思路:
1. 判断是否能让两个顶点连在一起.
2. 生成树的个数.
注意: 的还有0 0 也是一棵树
这题解出来了,可是is it a tree?竟然超时,有待思考
#include <iostream> using namespace std; #define MAX 100010 int mark[MAX], set[MAX]; int find(int n) { return set[n]==n?n:find(set[n]); } int Unioun(int u, int v) { int x, y; x = find(u); y = find(v); if (x!=y) { set[x] = y; return 1; } else return 0; } int main() { int u, v, flag, nc, i; while (1) { flag = 1; memset(mark, 0, sizeof(mark)); while (cin>>u>>v && (u!=-1&&v!=-1)) { if (u==0&&v==0) //0 0 也是树 { cout<<"Yes"<<endl; continue; } for (i=0; i<MAX; i++) set[i] = i; int max=-1, min=MAX; while (u||v) { if (u>max) max=u; if (v>max) max=v; if (u<min) min=u; if (v<min) min=v; mark[u] = mark[v] = 1; if (Unioun(u, v)==0) //判断是否能连接上 flag = 0; cin>>u>>v; } if (flag==0) cout<<"No"<<endl; else { nc = 0; for (i=min; i<=max; i++) { if (mark[i]&&set[i]==i)//记录是否只有一棵树 nc++; } if (nc==1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } if (u==-1 && v==-1) break; } return 0; }