信息学奥赛一本通 1389：亲戚第四章图论

长春高老师编程

401人浏览 · 2025-03-06 17:32:50

长春高老师编程 · 2025-03-06 17:32:50 发布

1389：亲戚

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的某个人所在家族的人数。

规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。

【输入】

第一行两个整数n，m（n≤100,000,m≤200,000），分别表示有n个人，m个信息。

以下m行：信息包含两种形式：

M a b：表示a和b具有亲戚关系。

Q a：要求输出a所在家族的人数。

【输出】

要求输出a所在家族的人数。

【输入样例】

【输出样例】

【解析】

并查集，详见代码：

#include<bits/stdc++.h>
using namespace std;
int fa[100005];//fa[i]表示i的祖先
int num[100005];//num[i]表示以i为祖先的家族人数
int n, m, x, y;
char c;
int Find(int x) { //找祖先
    if (fa[x] == x) return x;
    return fa[x] = Find(fa[x]);
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {//初始化
        fa[i] = i;//祖先是自己
        num[i] = 1;//人数为1
    }
    for(int i = 1; i <= m; i++) {
        cin >> c;
        if (c == 'M') {
            cin >> x >> y;
            x = Find(x);//找祖先
            y = Find(y);//找祖先
            if (x != y) {//祖先不同
                fa[y] = x;//合并
                num[x] += num[y];//人数合并
            }
        } else {
            cin >> x;
            x = Find(x);//找祖先
            cout << num[x] << "\n";//输出家族人数
        }
    }
    return 0;
}