Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我感觉是这样:TLE是list太慢了,用vector可以过;RE是因为dfs超栈,G++的栈VC的小(refer to faq)

Posted by frkstyc at 2005-11-02 22:51:52 on Problem 2230
In Reply To:Hawk大哥,我这个O(m)的复杂度的C++程序,G++ RE, C++ TLE,真的搞不明白了啦。。。。。。 Posted by:huicpc16 at 2005-11-02 21:47:14
> #include <iostream>
> #include <list>
> 
> using namespace std;
> 
> typedef struct vertc
> {
> 	int dest;
> 	int visit;
> }vert;
> 
> typedef list<vert> vlist;
> typedef vlist::iterator vptr;
> 
> void dfs(vlist *nodes, int nr)
> {
> 	for(vptr itr = nodes[nr].begin(); itr != nodes[nr].end(); itr ++)
> 	{
> 		if( itr->visit ) continue;
> 		itr->visit = 1;
> 		dfs(nodes, itr->dest);
> 	}
> 	printf("%d\n", nr + 1);
> }
> 
> int main()
> {
> 	int m,n,a,b,i;
> 	vert nvt;
> 	vlist *nodes;
> 
> 	scanf("%d%d", &n, &m);
> 	nodes = new vlist[n];
> 	nvt.visit = 0;
> 	for(i = 0; i < m; i ++)
> 	{
> 		scanf("%d%d", &a, &b);
> 		a--, b--;
> 		nvt.dest = b;
> 		nodes[a].push_back(nvt);
> 		nvt.dest = a;
> 		nodes[b].push_back(nvt);
> 	}
> 	dfs(nodes, 0);
> 	delete []nodes;
> 
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator