1118 Birds in Forest (25分)

题目链接：1118 Birds in Forest (25分)

题意

给出N个照片上的鸟，同一照片上的鸟在同一颗树上。鸟的编号从1递增。判断有多少颗树，和鸟的数量。判断两只鸟是否在同一颗树上。

分析

考察并查集。编号递增，所以设置个maxVal输入时计算最大编号就可以了，然后在设置个并查集数组，根元素的值等于根元素。输入时将同一个照片上的鸟的编号合并。集合的数量就为树的数量。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */using namespace std;
const int maxn = 10010;
int f[maxn];
int findRoot(int x);
void Union(int a, int b);
int main(int argc, char** argv) {
    int n, k, t, x, x2, maxVal = -1;scanf("%d", &n);for (int i = 1; i <= maxn; i++)f[i] = i;for (int i = 0; i < n; i++) {
    scanf("%d", &t);if (t != 0) {
    scanf("%d", &x);maxVal = max(maxVal, x);}for (int j = 1; j < t; j++) {
    scanf("%d", &x2);Union(x, x2);maxVal = max(maxVal, x2);}}int cnt = 0;for (int i = 1; i <= maxVal; i++) {
    if (f[i] == i)cnt++;}printf("%d %d\n", cnt, maxVal);scanf("%d", &k);for (int i = 0; i < k; i++) {
    scanf("%d%d", &x, &x2);if (findRoot(x) == findRoot(x2))printf("Yes\n");elseprintf("No\n");}return 0;
}
int findRoot(int x) {
    int a = x;while (x != f[x])x = f[x];while (a != f[a]) {
    int t = f[a];f[a] = x;a = t;}return x;
}
void Union(int a, int b) {
    int fa = findRoot(a);int fb = findRoot(b);if (fa < fb) {
    f[fa] = fb;} else {
    f[fb] = fa;}
}