PKU 1611 - The Suspects (并查集)

题意

问有几个人被感染。

思路

把一组的人全部并在一起,同时计算那组的人数。

代码

int f[MAXN], rnk[MAXN];
 
int Find(int a)
{
    return f[a] = (f[a] == a ? a : Find(f[a]));
}
 
void Union(int a, int b)
{
    int x = Find(a), y = Find(b);
    if (x == y) return;
    if (rnk[x] >= rnk[y])
    {
        f[y] = x;
        rnk[x] += rnk[y];
    }
    else
    {
        f[x] = y;
        rnk[y] += rnk[x];
    }
}
 
int main()
{
    //ROP;
    int n, m;
    while (scanf("%d%d", &n, &m), n+m)
    {
        for (int i = 0; i < n; i++) f[i] = i, rnk[i] = 1;
        for (int i = 0; i < m; i++)
        {
            int tmp, fir;
            scanf("%d%d", &tmp, &fir);
            for (int j = 1; j < tmp; j++)
            {
                int num;
                scanf("%d", #);
                Union(fir, num);
            }
        }
        printf("%d\n", rnk[Find(f[0])]);
    }
    return 0;
}

Powered by Jekyll and Theme by solid