题目:题目链接
题意:给出你每对点的链接情况,问你最后构成的是不是一棵树
分析:并查集,判断是不是有多个根即可(按照树 的定义,只有一个根。每个子节点只能有一个父节点)。对了,没
有节点也算树,就是说空树也算:
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; } #define N 10005 int father[N],vis[N]; int find(int x) { int r = x; while(father[r] != r) r = father[r]; return r; } void merge(int fx,int fy) { if (fx < fy) father[fx] = fy; else father[fy] = fx; } int main() { int n, m; int cnt = 1; int flag; int max = -1; int fa,fb; while(cin >> n >>m) { if(n == -1&&m == -1) return 0; if(n==0 && m==0) { cout<<"Case "<<cnt++<<" is a tree."<<endl; continue; } flag = 0; for(int i = 1; i <= N; i++) { father[i] = i; vis[i] = 0; } if(n > max) max=n; if(m > max) max = m; vis[n] = vis[m]=1; fa = find(n); fb = find(m); if(fa == fb) flag++; else merge(fa, fb); while(cin >> n >> m) { if(n == 0&& m == 0) break; if(n > max) max=n; if(m > max) max=m; fa = find(n); fb = find(m); vis[n] = vis[m] = 1; if(fa == fb) flag++; else merge(fa, fb); } for( int i = 1; i <= max; i++ ) if(vis[i] && father[i] == i ) { flag++; } if(flag==1) cout<<"Case "<<cnt++<<" is a tree."<<endl; else cout<<"Case "<<cnt++<<" is not a tree."<<endl; } return 0; }