http://acm.hdu.edu.cn/showproblem.php?pid=1272
//1264198 2009-04-12 16:58:37 Accepted 1272 31MS 1096K 1573 B C++ no way #include<iostream> using namespace std; struct Node { long parent; long hight; }; Node polong[100001]; bool visited[100001];//标记某点出现过 long find(long x) //查找根 { while(x != polong[x].parent) x = polong[x].parent; return x; }
void merge(long a,long b)//合并 { if(polong[a].hight == polong[b].hight) { polong[a].parent = b; polong[b].hight += 1; } else if(polong[a].hight > polong[b].hight) polong[b].parent = a; else polong[a].parent = b; }
long main() { long maxn,minn,a,b,sign,i; while(scanf("%ld%ld",&a,&b)!=EOF) { if(a==-1 && b==-1) break; if(a==0 && b==0) { cout<<"Yes"<<endl; continue; } for(i=1;i<=100000;i++)//注意注意 { polong[i].parent = i; polong[i].hight = 1; visited[i] = 0; }
maxn = 0; minn = 100000; sign = 0;
do{ if(a > maxn) maxn = a; if(b > maxn) maxn = b; if(minn > a) minn = a; if(minn > b) minn = b; visited[a] = 1; visited[b] = 1; a = find(a); b = find(b); if(a == b) //根相同表示有回路~ { sign = -1; break; } else merge(a,b);
scanf("%ld%ld",&a,&b); if(a==0 && b==0) break; }while(1);
if(sign == -1) //还未输入完 { do{ scanf("%ld%ld",&a,&b); if(a==0 && b==0) break; }while(1); }
if(sign == 0) //没有回路,查看是否都在一个集合 { for(i=minn;i<=maxn;i++) if(visited[i] == 1 && polong[i].parent == i) sign ++; }
if(sign == 1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
|