Description
Each of the M lanes of the Park of Polytechnic University of Bucharest connects two of the N crossroads of the park (labeled from 1 to N). There is no pair of crossroads connected by more than one lane and it is possible to pass from each crossroad to each other crossroad by a path composed of one or more lanes. A cycle of lanes is simple when passes through each of its crossroads exactly once.Input
On the first line of the input file the number T of the test cases will be given. Each test case starts with a line with the positive integers N and M, separated by interval (4 <= N <= 4444). Each of the next M lines of the test case contains the labels of one of the pairs of crossroads connected by a lane.Output
For each of the test cases, on a single line of the output, print the length of a maximal simple cycle.Sample Input
1 7 8 3 4 1 4 1 3 7 1 2 7 7 5 5 6 6 2
Sample Output
4
Source
Southeastern European Regional Programming Contest 2009#include#include #include #include #include using namespace std; #define N 5000 vector q[N]; int vis[N]; int n,m; int ans; void dfs(int a,int pos) { int i; vis[a]=pos; for(i=0;i ans) //例如環 1 2 3 4 1 ,vis[1]=1,vis[4]=4,下一次4與 //1相連,但是已經vis[1],所以環的大小 vis[4]-vis[1]+1 ans=vis[a]-vis[x]+1; } } int main() { int i,t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(vis,0,sizeof(vis)); int x,y; for(i=1;i<=n;i++) //記得清空上次的數據 q[i].clear(); while(m--) { scanf("%d%d",&x,&y); q[x].push_back(y); //q[x]存與x的臨邊 q[y].push_back(x); //同理 } ans=0; for(i=1;i<=n;i++) if(!vis[i]) //因為一個點就會出現一次,即使兩個環有共同邊, //那麼在公共邊那個分叉點還是會分別進行dfs的 dfs(i,1); //不加下面會錯 if(ans<=2)//一個環需要3個點,但是我郁悶了,如果沒有環的話 //怎麼會有vis[x]已經標記了呢?(此時ans=0啊)難道有數據類似 // a b b a (⊙o⊙)… ans=0; printf("%d\n",ans); } return 0; }