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;
}
|
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
導航
統計
- 隨筆: 84
- 文章: 7
- 評論: 49
- 引用: 0
常用鏈接
留言簿(6)
隨筆分類
隨筆檔案
文章分類
文章檔案
相冊
百事百通
搜索
積分與排名
最新評論

閱讀排行榜
評論排行榜
|
|