洛谷 - P3367 [模板] 并查集¶

洛谷 - P3367 [模板] 并查集¶

题目描述¶

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式¶

第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式¶

如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N

输入输出样例¶

输入 #1

输出 #1

N
Y
N
Y

说明/提示¶

时空限制：1000ms,128M

数据规模：

对于30%的数据，N<=10，M<=20；

对于70%的数据，N<=100，M<=1000；

对于100%的数据，N<=10000，M<=200000。

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <queue>
#include <algorithm>

using namespace std;

int n = 10005;
vector<int> parent(n);
vector<int> rankNum(n); //树的高度

//初始化
void init(int n)
{
    for (int i = 0; i <= n; ++i) {
        parent[i] = i;
    }
}

//查询操作
int find(int x)
{
    if (parent[x] == x) return x;
    else return parent[x] = find(parent[x]);
}

//合并x和y所属的集合
void unite(int x, int y)
{
    x = find(x);
    y = find(y);
    //如果x和y所属的集合相同，无需操作
    if (x == y) return;
    //按高度合并
    if (rankNum[x] < rankNum[y]) parent[x] = y;
    else {
        parent[y] = x;
        if (rankNum[x] == rankNum[y]) ++rankNum[x];
    }
}

//查询x和y是否属于同一个集合
bool isSame(int x, int y)
{
    return find(x) == find(y);
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int num;
    cin >> n >> num;
    init(n);
    while (num--) {
        int seq, x, y;
        cin >> seq >> x >> y;
        if (seq == 1) unite(x, y);
        else {
            if (isSame(x, y)) cout << "Y" << endl;
            else cout << "N" << endl;
        }
    }

    return 0;
}

模板题目。