这道题要求的是每两个点能到达且只有一条路。
思考 1. 怎么判断任意两点可以到达？ 2. 怎么判断任意两点只有一条路？
解决方法： 1. 如果所有路连通，那么所有路只有一个父亲。 2. 任意两点在最开始的时候是不同根，在当前它们有在搜索属于哪个根的时候，如果根相同那么有环。说明从这两个点出发有 两种方式到达其它同根的点。
注意： 1. 由于不知道有几个节点，要用visit记录。 2. 可能出现0 0 的情况，不过也是满足题意。
有两种方式 1. 递归
#include<cstdio> #define Max 100004 int root[Max]; int visit[Max]; int union_find(int x) { //return x == root[x] ? x : (root[x] = union_find(root[x])); int _x = x,temp; while(root[_x] != _x) _x = root[_x]; while(root[x] != x){ temp = root[x]; root[x] = _x; x = temp; } return _x; } int main() { // freopen("in.txt","r",stdin); int u,v; while(scanf("%d%d",&u,&v) != EOF && u != -1 && v != -1){ if(u == 0 && v == 0){ printf("Yes\n"); continue; } for(int i = 1;i < Max; i++){ root[i] = i; visit[i] = false; } root[u] = v; visit[u] = true; visit[v] = true; int flag = false; while(scanf("%d%d",&u,&v) != EOF && u && v){ int _u = union_find(u); int _v = union_find(v); visit[u] = true; visit[v] = true; if(_u == _v) flag = true; else { root[_u] = _v; } } int r = 0; for(int i = 1;i < Max; i++){ if(visit[i] && root[i] == i) r++; } if(flag == 0 && r == 1) printf("Yes\n"); else printf("No\n"); } return 0; }