[模板] 並查集

 

 

 

 

 

#include <iostream>
using namespace std;
const int MAXN = 1e4   10;
int arr[MAXN];
int N, M;
void init(int N)    //初始化根節點為自己
{
for(int i = 1; i <= N; i  )
arr[i] = i;
}
int findfather(int x)       //尋父節點(根節點)
{
if(arr[x] == x)
return x;
return arr[x] = findfather(arr[x]);     //尋找過程中路徑壓縮 全部更新為根節點 提升查詢速度
}
bool checkin(int x, int y)      //查是否在一個集合中
{
x = findfather(x);
y = findfather(y);
if(x == y)
return true;
return false;
}
void join(int x, int y)     //若不在一個集合中 更新結點
{
x = findfather(x), y = findfather(y);
if(x != y)
arr[x] = y;
}
int main()
{
ios::sync_with_stdio(false);
cin>>N>>M;
init(N);
int z, x, y;
while(M--)
{
cin>>z>>x>>y;
if(z == 1)
{
join(x, y);
}
else 
{
if(checkin(x, y))
cout<<"Y"<<endl;
else
cout<<"N"<<endl;
}
}
return 0;
}