HDU 1272

• 无向图用并查集判断是否成环.
• 坑点：仅仅考虑了根节点相同(有回路)的情况,而忽略了有多个连通分量,也是不满足 任意两个房间有且仅有一条路径相同

  #include <iostream>
  #include <string.h>
  using namespace std;
  
  const int maxn = 1e5+10;
  
  int pre[maxn];
  int vis[maxn];
  bool flag;
  int maxnum;
  void init() {
  	for (int i=0; i<maxn; i++) pre[i] = i;
  	memset(vis,0,sizeof vis);
  	flag = true;
  	maxnum = 0;
  }
  int find(int x) {
  	if (x == pre[x]) return  x;
  	return pre[x] = find(pre[x]);
  }
  
  void merge(int a,int b) {
  	int ra = find(a);
  	int rb = find(b);
  	if (ra == rb) flag = false;
  	else pre[ra] = rb;
  }
  int u,v;
  int main() {
  //	freopen("a.txt","r",stdin);
  	init();
  	while ( scanf("%d%d",&u,&v) ) {
  		if ( u == -1 && v == -1 ) return 0;
  
  		if ( u == 0 && v == 0 ) {
  			int cnt = 0;
  			for (int i=1; i<=maxnum; i++) 
  				if (vis[i] && pre[i] == i) cnt++;
  			
  			if (flag && cnt<=1) printf("Yes\n");
  			else printf("No\n");
  			init();
  			continue;
  		}
  		maxnum = max(maxnum , max(u,v));
  		vis[u] = 1;
  		vis[v] = 1;
  		if (u != v) merge(u,v);
  	}
  	return 0;
  }