POJ 3895 - Cycles of Lanes

http://poj.org/problem?id=3895

概要

頂点数 \(N\) の連結な無向グラフが与えられる。 このグラフのシンプルな閉路のうち、最大のものの長さを答える。

制約

• \(4 \le N \le 4444\)
• 各辺は高々1つのシンプルな閉路にしか属さない

解法

2つ目の制約が非常に強く、単に DFS して、その最中に既に訪れたことのあるノードに到達したら そこまでの経路が1つの閉路になっているので、そのサイズを計算して最大値をとればいい。 閉路のサイズは最低でも3であることに注意する。

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 int ans;
 6 void dfs(const vector<vector<int> >& g, int u, int prev, int depth, vector<int>& visited)
 7 {
 8   if (visited[u] == -1) {
 9     visited[u] = depth;
10     for (vector<int>::const_iterator it = g[u].begin(); it != g[u].end(); ++it) {
11       if (*it != prev) {
12         dfs(g, *it, u, depth+1, visited);
13       }
14     }
15   } else {
16     ans = max(ans, depth - visited[u]);
17   }
18 }
19 
20 int main()
21 {
22   ios::sync_with_stdio(false);
23   int T;
24   cin >> T;
25   while (T-- > 0) {
26     int N, M;
27     cin >> N >> M;
28     vector<vector<int> > g(N);
29     for (int i = 0; i < M; i++) {
30       int u, v;
31       cin >> u >> v;
32       --u;  --v;
33       g[u].push_back(v);
34       g[v].push_back(u);
35     }
36 
37     ans = 0;
38     vector<int> visited(N, -1);
39     dfs(g, 0, -1, 0, visited);
40     cout << ans << endl;
41   }
42   return 0;
43 }