poj 3895(求无向图的最大简单环）

思想很简单，就是dfs,并且用一个数组记录到该节点所走过的长度，然后如果遇到已经走过的，就说明存在环了，更新一下ans。

 1 /*************************************************************************
 2     > File Name: poj3895.cpp
 3     > Author: syhjh
 4     > Created Time: 2014年03月02日 星期日 21时06分39秒
 5  ************************************************************************/
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 using namespace std;
11 
12 const int MAXN = (5000 + 50);
13 struct Edge {
14     int v, next;
15 } edge[MAXN << 1];
16 
17 int n, m, NE, ans;
18 int head[MAXN];
19 
20 void Insert(int u, int v) 
21 {
22     edge[NE].v = v;
23     edge[NE].next = head[u];
24     head[u] = NE++;
25 }
26 
27 bool mark[MAXN];
28 int dp[MAXN];
29 
30 void dfs(int u, int len)
31 {
32     mark[u] = true;
33     dp[u] = len;
34     for (int i = head[u]; i != -1; i = edge[i].next) {
35         int v = edge[i].v;
36         if (!mark[v]) {
37             dfs(v, len + 1);
38         } else {
39             ans = max(ans, dp[u] - dp[v] + 1);
40         }
41     }
42 }
43 
44 int main()
45 {
46     int _case;
47     cin >> _case;
48     while (_case--) {
49         cin >> n >> m;
50         NE = 0;
51         memset(head, -1, sizeof(head));
52         while (m--) {
53             int u, v;
54             cin >> u >> v;
55             Insert(u, v);
56             Insert(v, u);
57         }
58         ans = 0;
59         memset(mark, false, sizeof(mark));
60         for (int i = 1; i <= n; i++) {
61             if (!mark[i]) {
62                 dfs(i, 1);
63             }
64         }
65         if (ans <= 2) {
66             cout << 0 << endl;
67         } else
68              cout << ans << endl;
69     }
70     return 0;
71 }

View Code