1118 Birds in Forest（25 分）

并查集，把每个照片的第一个鸟作为合并的第一个

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
const int maxn = 1e5 + 10;
int father[maxn];
set<int>bird;
bool isroot[maxn];
int findfather(int x)
{
    int a = x;
    while (x != father[x])x = father[x];
    while (a != father[a])
    {
        int z = a;
        a = father[a];
        father[z] = x;
    }
    return x;
}
void Union(int a, int b)
{
    int fa = findfather(a);
    int fb = findfather(b);
    if (fa != fb)
    {
        father[fa] = fb;
    }
}
int maxb = 0;
int main()
{
    int n;
    for (int i = 0; i < maxn; i++)father[i] = i;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int k, b;
        scanf("%d", &k);
        int x;
        scanf("%d", &x);
        k--;
        bird.insert(x);
        maxb = max(maxb, x);
        while (k--)
        {
            scanf("%d", &b);
            Union(x, b);
            bird.insert(b);
            maxb = max(maxb, b);
        }
    }
    for (int i = 1; i <= maxb; i++)
    {
        isroot[findfather(i)] = true;
    }
    int root = 0;
    for (int i = 1; i <= maxb; i++)root += isroot[i];
    printf("%d %d\n", root, bird.size());
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int b1, b2;
        scanf("%d%d", &b1, &b2);
        if (findfather(b1) == findfather(b2))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}