neuq-acm预备队训练week 9 P3367 【模板】并查集

题目描述

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

输入格式

解题思路

并查集的用法

AC代码

#include <bits/stdc++.h>
using namespace std;
#define Max 1000001
int zi,xi[Max],yi[Max],Fa[Max];
int find(int x);
bool qu(int u, int v);
int main()
{
    int i,m;
    cin>>i>>m;
    for(int j=1;j<=m;j++)
    {
        Fa[j]=j;
    }
    for(int j=1;j<=m;j++)
    {
        cin>>zi>>xi[j]>>yi[j];
        if(zi==1)
        {
            qu(xi[j],yi[j]);
        }
        if(zi==2)
        {
            if(find(xi[j])==find(yi[j])) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
        }
    }
}
bool qu(int u, int v)
{
    u = find(u), v = find(v);
    if (u == v) return true;
    Fa[u] = v;
    return false;
}
int find(int x)
{
    if (Fa[x] == x) return x;
    else return Fa[x] = find(Fa[x]);
}