随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:    判断是否为树,即无环联通图。    
 4 How to Do:    并查集
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 #define MAXSIZE 100002
11 int pre[MAXSIZE];
12 bool chose[MAXSIZE];
13 int findSet(int x){
14     if(x!=pre[x])
15         pre[x]=findSet(pre[x]);
16     return pre[x];
17 }
18 void init(){
19     memset(chose,false,sizeof(chose));
20     int i;
21     for(i=0;i<100002;i++)
22         pre[i]=i;
23 }
24 int main(){
25     //freopen("in.txt","r",stdin);
26     int m,n,point,line,flag=1;
27     while (scanf("%d%d",&m,&n)!=EOF){
28         if(m==0){//此处巨坑爹 WA了多次
29             puts("Yes");
30             continue;
31         }
32         if(m==-1&&n==-1)
33             break;
34         init();    point=line=0;
35         do {
36             line++;
37             int a=findSet(m);
38             int b=findSet(n);
39             if(!chose[a]){
40                 chose[a]=true;    point++;
41             }
42             if(!chose[b]){
43                 chose[b]=true;    point++;
44             }
45             if(a!=b)
46                 pre[a]=b;
47             else
48                 flag=0;
49         } while(scanf("%d%d",&m,&n)&&(m&&n));
50         if (flag&&line+1==point)//一定注意图的连通性,第一次就WA了
51             printf("Yes\n");
52         else
53             printf("No\n");
54     }
55     return 0;
56 }
57 
posted on 2012-03-15 18:27 Leo.W 阅读(201) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理