poj 并查集

水题

题意：就是找一共有多少个人感染了，0是感染学生的编号。

#include <stdio.h>
#include <string.h>
#define maxn 30005

int m,n;
int belg[ maxn ];

int Find(int x)
{
    int _x=x,_b;
    while( _x != belg[ _x ] )
        _x = belg[ _x ];
    while( x != belg[ x ] )
    {
        _b = belg[ x ];
        belg[ x ] = _x;
        x = _b;
    }
    return _x;
}

void unio(int x,int y)
{
    int root1 = Find(x);
    int root2 = Find(y);
    if( root1 != root2 ) belg[root2] = root1;
}

int main()
{
  //  freopen("in.txt","r",stdin);
    int a,b,c,ans;
    while(scanf("%d%d",&m,&n),m||n)
    {
        for( int i = 0 ; i <= m ; i++ )
            belg[ i ] = i;
        for( int i = 0 ; i < n ; i++ )
        {
            scanf("%d%d",&a,&b);
            for( int j = 0 ; j < a-1 ; j++ )
            {
                scanf("%d",&c);
                unio(b,c);
            }
        }
        ans = 0;
        a = Find(0);
        for(int i = 0 ; i <= m ; i++ )
            if(Find(i)==a) ans++;
        printf("%d
",ans);
    }
    return 0;
}

poj 2492

http://poj.org/problem?id=2492

题意：给出m组关系，要你判断这里面有没有同性恋。

这是并查集的一个高级用法，但是我是第一次用并查集的高级用法，现在也还不是很理解这是为什么，什么意思。还得好好的模拟，想一想，感觉身体被掏空

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 5005
 4 
 5 
 6 int belg[ maxn ];
 7 bool kind[ maxn ],sign;
 8 
 9 int Find(int x, bool &s)
10 {
11     int  _x, h = x;
12     bool s1, s2;
13 
14     while ( belg[h]!=h )
15     {
16         s = s^kind[h];   
17 
18          //这里的目的是看s也就是当前的x是不是与他的祖父是相同性别的。
19 
20         h = belg[h];
21     }
22 
23     s1 = s;
24     while ( belg[x]!=x )
25     {
26         _x = belg[x];
27         belg[x] = h;
28         s2 = kind[x];
29         kind[x] = s1;    //更新kind[ x ],因为最开始的x的kind就是s1，而之后的kind[ x ]就应该是s1与s2的^运算
30 
31         s1 = s1^s2;
32         x = _x;
33     }
34 
35     return h;
36 }
37 
38 
39 void unio(int x,int y)
40 {
41     bool su,sv;
42     int root1 = Find( x ,sv=false);
43     int root2 = Find( y ,su=false);
44     if( root1 == root2 ) sign = sv^su;
45     else {
46             belg[ root2 ] = root1;
47             kind[ root2 ] = !(su^sv);
48     }
49 }
50 
51 int main()
52 {
53     freopen("in.txt","r",stdin);
54     int t,nu = 0,a,b,m,n;
55     scanf("%d",&t);
56     while(t--)
57     {
58         sign = true;
59         nu++;
60         scanf("%d%d",&m,&n);
61         memset( kind , false , sizeof( kind ) );
62         for( int i = 0 ; i <= m ; i++ )
63             belg[ i ] = i;
64         for( int i = 0 ; i < n ; i++ )
65         {
66             scanf("%d%d",&a,&b);
67             if(sign) unio(a,b);
68         }
69          printf("Scenario #%d:
",nu);
70         if(sign)
71             printf("No suspicious bugs found!

");
72         else
73             printf("Suspicious bugs found!

");
74 
75     }
76     return 0;
77 }

poj 2498

poj 1988

http://poj.org/problem?id=1988

题意：就是给你一群盒子，有两个操作，M就是move，也就是把x盒子移到y盒子的上面。

c就是查询，查询x下面一共有多少个盒子

移动，是指x盒子及其上面的所有的盒子都一起移动到y盒子的上面去。

这个题我原来做过，那个时候不会并查集，然后就用一个结构体来记录其最下面的点，最上面的点，以及这个点下面一共有多少个盒子，然后每次维护。这样就是超时.......然后最近学了并查集，但因为对其理解还不是特别深，不是很会灵活应用，所有也不知道怎么用。最后还是看别人博客，理解别人的思路，再去自己写

思路：维护两个数组，一个是当前盒子下面一共有多少个盒子，以及自己最上面的盒子的个数。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 100030
 4 
 5 int belg[ maxn ],rank[ maxn ],top[ maxn ];
 6 
 7 int Find(int x)
 8 {
 9     if(belg[x]!=x)
10     {
11         int fa = belg[x];    //每次压缩的时候，顺便更新当前点下面的合资数。
12         belg[x] = Find(fa);
13         rank[x] += rank[fa];
14     }
15     return belg[x];
16 }
17 
18 void uion(int x,int y)
19 {
20     int root1 = Find( x );
21     int root2 = Find( y );
22     if( root1 != root2 )
23     {
24         belg[ root1 ] = root2;    //把x移到y的上面，以及更新x的下面的数量和y最上面的的数量。
25         rank[ root1 ] = top[ root2 ] + 1;   
26         top[ root2 ] += top[ root1 ]+1;
27     }
28 
29 }
30 
31 int main()
32 {
33 //    freopen("in.txt","r",stdin);
34     int t,a,b;
35     char x;
36     scanf("%d",&t);
37     for(int i = 0 ; i <= t ; i++)
38         belg[ i ] = i;
39     while(t--)
40     {
41         scanf("%s",&x);
42         if(x=='M')
43         {
44             scanf("%d%d",&a,&b);
45             uion( a , b );
46         }
47         else
48         {
49             scanf("%d",&a);
50             Find( a );
51             printf("%d
",rank[ a ] );
52         }
53     }
54     return 0;
55 }

poj 1988

poj 2912

http://poj.org/problem?id=2912

题意：有n个人在玩石头剪刀布，这其中就有一个是裁判，而且每一个人都只会出一种手势，要你求是否可以判断出裁判是哪个，并且输出在第几个语句可以判断。

这个题有点像那个食物链的题目，我在判断语句时，也是采取了和食物链一样的写法。

思路：就是枚举每一个人当为裁判，然后进行判断，看看其他与这个裁判无关的语句，是否有矛盾，如果没有矛盾，说明这个人有可能是裁判，如果有，那么这个人就肯定不能当裁判，最后如果没有符合条件的，就输出impossible，如果超过了一个人就输出Can not determine，如果恰好是一个人就输出可以找到，并且把裁判和在哪个语句中可以判断出，在哪个语句中可以判断出的话，这个就是在看最后一个产生矛盾的语句是在哪产生的，因为但枚举的不是这个裁判的时候，这个裁判的语句就会被合并，当找到最后一个矛盾产生的语句时，也就可以判断这个裁判是在哪里被找出来的了。

关于那些语句看不懂可以先去看看我写的食物链。Poj 1182

http://www.cnblogs.com/Tree-dream/p/5709880.html

  1 #include <stdio.h>
  2 #include <string.h>
  3 #define maxn 2005
  4 
  5 struct note{
  6     int x,mark,y;
  7 }s[ maxn ];
  8 
  9 int m,n,belg[ maxn * 3 ];
 10 bool mark[ maxn * 3 ];
 11 
 12 int Find(int x)
 13 {
 14     int _x=x,_b;
 15     while(_x!=belg[_x])
 16     {
 17         _x=belg[_x];
 18     }
 19     while(x!=belg[x])
 20     {
 21         _b=belg[x];
 22         belg[x]=_x;
 23         x=_b;
 24     }
 25     return _x;
 26 }
 27 
 28 bool judge(int x,int y) {
 29     if(Find(x)==Find(y))
 30         return true;
 31     else return false;
 32 }
 33 
 34 void unite(int x,int y)
 35 {
 36     int root1=Find(x);
 37     int root2=Find(y);
 38     if(root1!=root2) belg[root1]=root2;
 39 }
 40 
 41 void init()
 42 {
 43     for( int i = 0 ; i <= 3*m ; i++ )
 44         belg[ i ] = i;
 45 }
 46 
 47 int main()
 48 {
 49  //   freopen("in.txt","r",stdin);
 50     int a,b;
 51     char c;
 52     while(scanf("%d%d",&m,&n)!=EOF)
 53     {
 54         init();
 55         for(int i = 1 ; i <= n ; i++ )
 56         {
 57             scanf("%d%c%d",&a,&c,&b);
 58             getchar();
 59             if(c=='=')
 60             {
 61                 s[ i ].x = a;
 62                 s[ i ].y = b;
 63                 s[ i ].mark = 1;
 64             }
 65             if(c=='<')
 66             {
 67                 s[ i ].x = b;
 68                 s[ i ].y = a;
 69                 s[ i ].mark = 0;
 70             }
 71             if(c=='>')
 72             {
 73                 s[ i ].x = a;
 74                 s[ i ].y = b;
 75                 s[ i ].mark = 0;
 76             }
 77         }
 78         int i,sign = 0,falg = 0,y = 0,j;
 79         for( i = 0 ; i < m ; i++ )
 80         {
 81             init();
 82            for(j = 1 ;j <= n ; j++ )
 83            {
 84                if(s[ j ].x != i && s[ j ].y != i)
 85                {
 86                    if(s[ j ].mark == 1)
 87                    {
 88                        if(judge(s[ j ].x,s[ j ].y + m )||judge(s[ j ].x,s[ j ].y + 2 * m))
 89                        {
 90                            if( j > y ) y = j;
 91                            break;
 92                        }
 93                        else
 94                        {
 95                            unite(s[ j ].x , s[ j ].y);
 96                            unite(s[ j ].x + m , s[ j ].y + m);
 97                            unite(s[ j ].x + 2 * m , s[ j ].y + 2 * m);
 98                        }
 99                    }
100                    else
101                    {
102                        if(judge( s[ j ].x , s[ j ].y)||judge(s[ j ].x , s[ j ].y + 2 * m))
103                        {
104 
105                            if( j > y ) y = j;
106                            break;
107                        }
108                        else
109                        {
110                            unite( s[ j ].x , s[ j ].y + m );
111                            unite( s[ j ].x + m , s[ j ].y + 2 * m );
112                            unite( s[ j ].x + 2 * m , s[ j ].y );
113                        }
114                    }
115                }
116            }
117            if(j == n+1)
118            {
119                falg ++;
120                sign = i;
121            }
122         }
123         if(falg == 0) printf("Impossible
");
124         else if(falg > 1) printf("Can not determine
");
125         else printf("Player %d can be determined to be the judge after %d lines
",sign,y);
126 
127 
128     }
129     return 0;
130 }

poj 2912

HDU 3038

题意：n次询问，给出a到b区间的总和，问这n次给出的总和中有几次是和前面已近给出的是矛盾的。

思路：并查集，维护一个之间和的序列就可以。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define maxn 200020
 4 
 5 int belg[ maxn ],sum[ maxn ];
 6 
 7 int Find(int x)
 8 {
 9     if(x!=belg[x])
10     {
11         int fa = belg[ x ];
12         belg[ x ] = Find(fa);
13         sum[ x ] += sum[ fa ];
14     }
15     return belg[ x ];
16 }
17 
18 int main()
19 {
20   //  freopen("in.txt","r",stdin);
21     int m,n,a,b,c;
22 
23     while(scanf("%d%d",&m,&n)!=EOF)
24     {
25         int ans=0;
26         for( int i = 0 ; i <= m ; i++ )
27             belg[ i ] = i,sum[  i ] = 0;
28         for( int i = 0 ; i < n ; i++ )
29         {
30             scanf("%d%d%d",&a,&b,&c);
31             b--;             //这里记得--
32             int root1 = Find(a),root2 = Find(b);
33             if(root1 == root2)
34             {
35                 if(sum[ b ]-sum[ a ] != c) ans++;
36             }
37             else
38             {
39                     belg[ root2 ] = root1;
40                     sum[ root2 ] = sum[ a ]- sum[ b ] + c;
41             }
42         }
43         printf("%d
",ans);
44     }
45     return 0;
46 }

hdu 3038