poj 3310 Caterpillar (树的直径+并查集判环+dfs判断连通性)
题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。
思路：一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过
环的话并查集就好。。
关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长？
于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。
具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一个to[]数组表示相连。。。to[u]=v,to[v]=u...
然后只要ok[i]或者ok[to[i]]满足其一就好。。。
又是1A，蛤蛤蛤蛤蛤，我好神啊（误
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月12日 星期二 20时27分28秒
4File Name :code/poj/3310.cpp
5 ************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=305;
32int n,m;
33vector < int >edge[N];
34int f[N];
35bool vis[N];
36bool die;
37int d[N];
38int to[N];
39int pre[N];//记录最长的路径。。。
40int lst,beg;
41bool ok[N];
42struct Edge
43{
44 int u,v;
45}e[N];
46void init()
47{
48 ms(to,-1);
49 ms(pre,-1);
50 ms(vis,false); //for dfs
51 ms(ok,false);
52 for ( int i = 1 ; i <= n ; i++) f[i] = i;
53 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
54}
55int root ( int x)
56{
57 if (x!=f[x]) f[x] = root (f[x]);
58 return f[x];
59}
60void merge( int x,int y)
61{
62 int rx = root(x);
63 int ry = root(y);
64 if (rx==ry) return ;
65 f[rx] = ry;
66}
67void dfs( int u)
68{
69 vis[u] = true;
70 int siz = edge[u].size();
71 for ( int i = 0 ; i < siz ; i++)
72 {
73 int v = edge[u][i];
74 if (vis[v]) continue;
75 dfs(v);
76 }
77}
78void bfs( int s)
79{
80 ms(d,0);
81 ms(vis,false);
82 ms(pre,-1);
83 queue<int>q;
84 q.push(s);
85 vis[s] = true;
86 while (!q.empty())
87 {
88 int u = q.front();q.pop();
89 int siz = edge[u].size();
90 for ( int i = 0 ; i < siz ; i++)
91 {
92 int v = edge[u][i];
93 if (vis[v]) continue;
94 // cout<<" u:"<<u<<" v:"<<v<<endl;
95 d[v] = d[u] + 1;
96 pre[v] = u;
97 vis[v] = true;
98 q.push(v);
99 }
100 }
101}
102int main()
103{
104#ifndef ONLINE_JUDGE
105 freopen("code/in.txt","r",stdin);
106#endif
107 int cas = 0 ;
108 while (scanf("%d",&n)!=EOF)
109 {
110 if (n==0) break;
111 scanf("%d",&m);
112 init();
113 die = false;
114 for ( int i =1 ; i <= m ; i++)
115 {
116 int u,v;
117 scanf("%d%d",&u,&v);
118// cout<<"u:"<<u<<" v:"<<v<<endl;
119 e[i].u =u;
120 e[i].v= v;
121 to[u] = v;
122 to[v] = u;
123 edge[u].push_back(v);
124 edge[v].push_back(u);
125 }
126 dfs(1); //判断连通性
127// cout<<"dfs die?"<<endl;
128 for ( int i = 1 ; i <= n ; i++)
129 {
130 if (!vis[i])
131 {
132 die = true;
133 break;
134 }
135 }
136 if (die)
137 {
138 printf("Graph %d is not a caterpillar.\n",++cas);
139 continue;
140 }
141 for ( int i = 1 ; i <= m ; i++)
142 {
143 int u = e[i].u;
144 int v = e[i].v;
145 if (root(u)==root(v)) //判环
146 {
147 die = true;
148 continue;
149 }
150 merge(u,v);
151 }
152// cout<<"union set die?"<<endl;
153 if (die)
154 {
155 printf("Graph %d is not a caterpillar.\n",++cas);
156 continue;
157 }
158 bfs(1);
159// for ( int i = 1 ;i <= n ; i++) cout<<" pre[i]:"<<pre[i]<<endl;
160 int mx = 0 ;
161 for ( int i = 1 ; i <= n ; i++)
162 {
163 if (d[i]>mx)
164 {
165 mx = d[i];
166 lst = i;
167 }
168 }
169 bfs(lst);
170// cout<<"bfs die?"<<endl;
171 mx = 0 ;
172 for ( int i = 1 ; i <= n ; i++)
173 {
174 if (d[i]>mx)
175 {
176 mx = d[i];
177 beg = i ;
178 }
179 }
180 int x = beg;
181// for ( int i = 1 ;i <= n ; i++) cout<<" pre[i]:"<<pre[i]<<endl;
182 while(x!=-1)
183 {
184 // cout<<"x:"<<x<<endl;
185 ok[x] = true;
186 x = pre[x];
187 }
188// cout<<"get pre die?"<<endl;
189 for ( int i = 1 ; i <= n ; i++)
190 {
191 if (ok[i]||ok[to[i]]) continue;
192// cout<<"i:"<<i<<endl;
193 die = true;
194 break;
195 }
196 if (die)
197 {
198 printf("Graph %d is not a caterpillar.\n",++cas);
199 continue;
200 }
201 printf("Graph %d is a caterpillar.\n",++cas);
202 }
203#ifndef ONLINE_JUDGE
204 fclose(stdin);
205#endif
206 return 0;
207}