并查集的几道题（hdu1198）（1232）（1272）（1598）

1232模板题

View Code

 1 #include <stdio.h>
 2 #include<string.h>
 3 int father[1001];
 4 int find(x)
 5 {
 6     if(x!=father[x])
 7     father[x] = find(father[x]);
 8     return father[x];
 9 }
10 void union1(int x,int y)
11 {
12     father[x] = y;
13 }
14 int main()
15 {
16     int i,j,k,n,m,a,b;
17     while(scanf("%d",&n)&&n)
18     {
19         scanf("%d",&m);
20         int num = 0;
21         for(i = 1 ; i <= n ; i++)
22         father[i] = i;
23         for(i = 1 ; i <= m ; i++)
24         {
25             scanf("%d%d",&a,&b);
26             int px = find(a);
27             int py = find(b);
28             if(px!=py)
29             union1(px,py);
30         }
31         for(i = 1; i <= n ; i++)
32         if(father[i]==i)
33         num++;
34         printf("%d\n",num-1);
35     }
36     return 0;
37 }

1272数据貌似挺水

View Code

 1 #include <stdio.h>
 2 #include<string.h>
 3 int father[100001],k[200001];
 4 int find(int x)
 5 {
 6     if(x!=father[x])
 7     father[x] = find(father[x]);
 8     return father[x];
 9 }
10 void union1(int x,int y)
11 {
12     father[x] = y;
13 }
14 int main()
15 {
16     int i,j,a,b,px,py,g,num;
17     while(scanf("%d%d",&a,&b)!=EOF)
18     {
19         if(a==-1&&b==-1)
20         break;
21         if(a==0&&b==0)
22         {
23             printf("Yes\n");
24             continue;
25         }
26         g = 0;
27         num = 0;
28         k[g++] = a;
29         k[g++] = b;
30         for(i = 1; i <= 100001 ; i++)
31         father[i] = i;
32         int flag = 0;
33         px = find(a);
34         py = find(b);
35         if(px!=py)
36         union1(px,py);
37         while(scanf("%d%d",&a,&b)!=EOF)
38         {
39             if(a==0&&b==0)
40             break;
41             k[g++] = a;
42             k[g++] = b;
43             px = find(a);
44             py = find(b);
45             if(px!=py)
46             father[px] = py;
47             else
48             if(a!=b)
49             flag = 1;
50         }
51         for(i = 0 ; i < g ; i++)
52         if(father[k[i]]==k[i])
53         num++;
54         if(num>1)
55         flag = 1;
56         if(flag)
57         printf("No\n");
58         else
59         printf("Yes\n");
60     }
61     return 0;
62 }

hdu1198用0和1表示四个方向有没有通道然后用并查集判联通

View Code

 1 #include <stdio.h>
 2 #include<string.h>
 3 int dis[12][4] = {{1,0,1,0},{1,0,0,1},{0,1,1,0},{0,1,0,1},{1,1,0,0},{0,0,1,1},{1,0,1,1},{1,1,1,0},{0,1,1,1},{1,1,0,1},{1,1,1,1}};
 4 int father[3001];
 5 int find(int x)
 6 {
 7     if(x!=father[x])
 8     father[x] = find(father[x]);
 9     return father[x];
10 }
11 void union1(int x,int y)
12 {
13     father[x] = y;
14 }
15 int main()
16 {
17     int i,j,k,n,m,px,py,x,y;
18     char c[51][51];
19     while(scanf("%d%d",&m,&n)!=EOF)
20     {
21         if(n<0&&m<0)
22         break;
23         int num = 0;
24         for(i = 1; i <= m ; i++)
25         {
26             getchar();
27             for(j = 1; j <= n ; j++)
28             c[i][j] = getchar();
29         }
30         for(i = 1 ; i <= n*m ; i++)
31         father[i] = i;
32         for(i = 1; i <= m ; i++)
33         {
34             for(j = 1 ; j <= n ; j++)
35             {
36                 x = c[i][j]-'A';
37                 y = c[i][j+1]-'A';
38                 if(j!=n)
39                 if(dis[x][3]==dis[y][2]&&dis[y][2]==1)
40                 {
41                     px = find((i-1)*n+j);
42                     py = find((i-1)*n+j+1);
43                     if(px!=py)
44                     union1(px,py);
45                 }
46                 if(i!=m)
47                 {
48                     y = c[i+1][j]-'A';
49                     if(dis[x][1]==dis[y][0]&&dis[y][0]==1)
50                     {
51                         px = find((i-1)*n+j);
52                         py = find(i*n+j);
53                         if(px!=py)
54                         union1(px,py);
55                     }
56                 }
57             }
58         }
59         for(i = 1 ; i <= n*m ; i++)
60         if(father[i]==i)
61             num++;
62         printf("%d\n",num);
63     }
64     return 0;
65 }

hdu1598

这题刚开始用并查集+BFS+优先队列写的一直WA 感觉是想麻烦了最后也没做出来搜到学姐的报告就仿照着写了写枚举吧

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #define N 1000001
 6 using namespace std;
 7 struct node
 8 {
 9     int u,v,w;
10 }q[1001];
11 int father[201];
12 int find(int x)
13 {
14     if(x!=father[x])
15     father[x] = find(father[x]);
16     return father[x];
17 }
18 void union1(int x,int y)
19 {
20     father[x] = y;
21 }
22 bool cmpp(struct node a,struct node b)
23 {
24     return a.w<b.w;
25 }
26 int main()
27 {
28     int i,j,k,m,n,u,v,w,o;
29     while(scanf("%d%d",&n,&m)!=EOF)
30     {
31         for(i = 0; i < m ; i++)
32         scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);
33         sort(q,q+m,cmpp);
34         scanf("%d", &o);
35         while(o--)
36         {
37             scanf("%d%d",&u,&v);
38             k = N;
39             for(i = 0 ; i < m ; i++)
40             {
41                 for(j = 1; j <= n ; j++)
42                 father[j] = j;
43                 for(j = i; j < m ; j++)
44                 {
45                     if(find(q[j].u)!=find(q[j].v))
46                     union1(find(q[j].u),find(q[j].v));
47                     if(find(u)==find(v))
48                     {
49                         w = q[j].w-q[i].w;
50 
51                         if(w<k)
52                         k = w;
53                         break;
54                     }
55                 }
56                 if(j==m)
57                 break;
58             }
59             if(k!=N)
60             printf("%d\n",k);
61             else
62             printf("-1\n");
63         }
64     }
65     return 0;
66 }