判断一个图是否为树（有向图以及无向图）
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<bitset>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 200007, M = 5000007, INF = 0x3f3f3f3f;
int fa[N], n, m;
bool vis[N];
int Find(int x)
{
if(fa[x] == x)return x;
return fa[x] = Find(fa[x]);
}
bool unions(int x, int y)
{
int fx = Find(x);
int fy = Find(y);
if(fx != fy){
fa[fy] = fx;//注意合并的是原来的点
return true;
}
return false;//有环，不是树
}
int x, y;
int kcase;
int main()
{
while(scanf("%d%d", &x, &y)){
kcase ++ ;
bool flag = true;
if(x < 0 || y < 0)
break;
if(x == 0 && y == 0){
printf("Case %d is a tree.\n", ++ kcase);
continue;
}
for(int i = 1; i < N; ++ i){
fa[i] = i;
vis[i] = 0;
}
while(!(x == y && y == 0)){
vis[x] = true;
vis[y] = true;
//!因为树只有一条边指向节点，根没有边指向根节点，所以如果有两个及以上的边指向它就说明不是树
if(Find(y) != y)
flag = false;
else if(unions(x, y) == 0){//有环，不是树
flag = false;
}
scanf("%d%d", &x, &y);
}
int tot = 0;
for(int i = 1; i < N; ++ i){
if(vis[i] && fa[i] == i)//找有几个根
tot ++ ;
/*if(tot > 1){
flag = 1;
break;
}*/
}
if(tot != 0 && tot != 1)flag = false;
//cout << tot << "ok" <<endl;
//入度大于1了或者成树林了
if(flag)
printf("Case %d is a tree.\n", kcase);
else
printf("Case %d is not a tree.\n", kcase);
}
return 0;
}