hdu 1829+hdu 1856(并查集）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1829

思路：就是同性别的合并在一个集合中，然后每次输入看u，v是否在同一个集合中。。。然后不知道为什么用路径压缩不可以写。。。一些就TLE了。。。无语了。。。orz。。。

View Code

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 const int MAXN=2000+20;
 7 int parent[MAXN];
 8 int mark[MAXN];
 9 int n,m;
10 
11 void Initiate(){
12     memset(mark,0,sizeof(mark));
13     for(int i=1;i<=n;i++){
14         parent[i]=i;
15     }
16 }
17 
18 int Find(int x){
19     int s=x;
20     while(s!=parent[s]){
21         s=parent[s];
22     }
23     return s;
24     /*
25     int s;
26     for(s=x;parent[s]>=0;s=parent[s]);
27     while(s!=x){
28         int tmp=parent[x];
29         parent[x]=s;
30         x=tmp;
31     }
32     return s;
33     */
34 }
35 
36 void Union(int R1,int R2){
37     int r1=Find(R1);
38     int r2=Find(R2);
39     if(r1<r2){
40         parent[r2]=r1;
41     }else
42         parent[r1]=r2;
43 }
44 
45 
46 int main(){
47     int _case,t=1;
48     scanf("%d",&_case);
49     while(_case--){
50         scanf("%d%d",&n,&m);
51         Initiate();
52         bool flag=true;
53         for(int i=1;i<=m;i++){
54             int u,v;
55             scanf("%d%d",&u,&v);
56             if(!flag)continue;
57             if(Find(u)==Find(v)){
58                 //找到同性的了。。。
59                 flag=false;
60                 continue;
61             }else {
62                 if(mark[u]==0)mark[u]=v;
63                 else Union(mark[u],v);//同性的并入一个集合
64                 if(mark[v]==0)mark[v]=u;
65                 else Union(mark[v],u);
66             }
67         }
68         printf("Scenario #%d:\n",t++);
69         if(!flag){
70             printf("Suspicious bugs found!\n");
71         }else {
72             printf("No suspicious bugs found!\n");
73         }
74         puts("");
75     }
76     return 0;
77 }

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1856

思路：就是合并集合。。。赤裸裸的并查集啊！！！！可我为什么wa了无数次啊！！！！orz....

View Code

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 const int MAXN=10000000+100;
 7 int parent[MAXN];
 8 int _count[MAXN];
 9 int n;
10 int MAX;
11 
12 void Initiate(){
13     for(int i=1;i<MAXN;i++){
14         parent[i]=-1;
15         _count[i]=1;
16     }
17 }
18 
19 int Find(int x){
20     int s;
21     for(s=x;parent[s]>=0;s=parent[s]);
22     while(s!=x){
23         int tmp=parent[x];
24         parent[x]=s;
25         x=tmp;
26     }
27     return s;
28 }
29 
30 
31 void Union(int R1,int R2){
32     int r1=Find(R1);
33     int r2=Find(R2);
34     if(r1!=r2){
35         parent[r2]=r1;
36         _count[r1]+=_count[r2];
37     }
38 }
39 
40 int main(){
41     while(~scanf("%d",&n)){
42         Initiate();
43         MAX=0;
44         for(int i=1;i<=n;i++){
45             int u,v;
46             scanf("%d%d",&u,&v);
47             Union(u,v);
48         }
49         for(int i=1;i<MAXN;i++){
50             if(parent[i]==-1&&_count[i]>MAX){
51                 MAX=_count[i];
52             }
53         }
54         printf("%d\n",MAX);
55     }
56     return 0;
57 }