模板目录

#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
  using namespace std;
  int f[10050],n,m; 
  
void init()//初始化，每个元素的上级就是自己 
{
    int i;
    for(i=1;i<=n;i++)
    f[i]=i;
 } 
    
 int find(int x)//查找元素的上级并路径压缩。 
 {
    if(f[x]==x) return x;
     return f[x]=find(f[x]);    
 
 }
    
 int Find(int x)  //非递归路径压缩 
{  
   int r=x;  
    while(r!=f[r])  
        r=f[r];  
      
    int i=x,j;  
    while(f[i]!=r)  
    {  
        j=f[i];  
        f[i]=r;  
        i=j;  
    }  
    return  r;  
}   
  
  
void HB(int x,int y)//合并集合，如果两个集合不在一个大集合里就合并 
{
    int t1=Find(x);
    int t2=Find(y);
    if(t1!=t2)   f[t2]=t1;    
  }  
   

int main()
{
    cin>>n>>m;
    init();    //初始化元素 
    int z,x,y;
    for(int i=1;i<=m;i++)//边输入边合并或判断 
    {
        cin>>z>>x>>y;         
        if(z==1)
          HB(x,y);
                  
        if(z==2)
        {
      
         // if(f[x]==f[y])  cout<<"Y"<<endl;//失败 ，有一个元素没路径压缩 
           if(Find(x)==Find(y))  cout<<"Y"<<endl;//成功 ，但增加时间 
                     else         cout<<"N"<<endl;        
        }
    }
    
    //for(int i=1;i<=n;i++)//测试用 
    //cout<<f[i]<<endl;
    return 0;
 }