The Suspects POJ - 1611 并查集水题

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
并查集的第二个题  哈哈 一遍过  其实很水  怕怕的过了 又有0ms的 气！！
这个题呢，就是说一个代号为0的成员，他携带病毒，如果说有人和0是一个队，那么整个团队就是带病毒的。
如果说和0一个团队的人同时也是另外一个团队的成员，那么另外一个团队的所有人都是感染病毒的。
最后要你求解的就是携带病毒的人的个数；
很水，很水，小小的用一下并查集就过去了。
就是有一个小细节，也是很简单的。开始跑了16ms；
后来看了网上的题解，为啥还要排名？？郁闷 尴尬,其实就是在过程中就把到达那个每一个点存在的人数记录下来，最后直接输出答案就可以了；
后来时间就变成0ms了
*/
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=3e4+7;
int n,pre[maxn],d,Rank[maxn],num[maxn];
bool vis[maxn];

int Find(int root)
{
    int son=root;
    while(root!=pre[root]) root=pre[root];
    while(son!=root)
    {
        int temp=pre[son];
        pre[son]=root;
        son=temp;
    }
    return root;
}

/**
这个题，有种强者更强的感觉，大概的意思就是让携带病毒的人比别人联系最大的永远做老大。
*/
void join(int root1,int root2)
{
    int x=Find(root1),y=Find(root2);
    if(x==y) return ;
    if(Rank[x]>Rank[y])
    {
        pre[y]=x;
        num[x]+=num[y];
    }
    else
    {
        pre[x]=y;
        if(Rank[x]==Rank[y]) Rank[y]++;
        /**
        现在是y大的情况；
        上面是大于的情况，所以下面如果存在的话呢，就一定是Rank[y]++;
        主要是pre[x]=y;完全进行了限制；
        原理和大于的情况是一样的，真的是好这个操作；
        */
        num[y]+=num[x];
    }
}

int main ()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        if(n==0&&m==0) break;
        if(m==0) {printf("1n");continue;}
        for(int i=0;i<n;i++)
        {
            pre[i]=i;///初始化；
            Rank[i]=0;
            num[i]=1;
        }
        while(m--)
        {
            int k;
            scanf("%d",&k);
            k--;
            int a;
            scanf("%d",&a);///先拿出第一个 然后一一合并；
            while(k--)
            {
                int b;
                scanf("%d",&b);
                join(a,b);
                a=b;
            }
        }
        /*int ans=0,key=Find(0);
        for(int i=0;i<n;i++)
        {
            if(Find(i)==key) ans++;///、这个就是最土鳖的一个一个查找了；
        }
        printf("%dn",ans);*/
        
        printf("%dn",num[key]);
    }
    return 0;
}