daize @ 2017-06-04 10:09:26

#include<cstdio>
#include<iostream>
using namespace std;
    int father[10000];
    int n,m,x,y;
void unionn(int x,int y)
{
    father[y]=x;
}
int find(int x)
{
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
int main()
{
    cin>>n>>m;
    int t;    
    for(int i=1;i<=n;i++)
    {
        father[i]=i;
    }
    for(int j=1;j<=m;j++)
    {
        scanf("%d%d%d",&t,&x,&y);
        int r1=find(x);
        int r2=find(y);
        if(t==1&&r1!=r2) unionn(r2,r1);
        else {if(r1!=r2) cout<<"N"<<endl; else cout<<"Y"<<endl;}
    }
    return 0;
}

by lydon @ 2017-06-15 20:56:13

include "cstdio"

include "iostream"

using namespace std;
int f[10005];
int find(int i)
{
    if(f[i]!=i)f[i]=find(f[i]);
    return f[i];
}
void join(int x,int y)
{
    if(find(x)!=find(y))f[find(f[x])]=find(y);
}
int main()
{
    int n,m,x,y,z;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    f[i]=i;
    for(int i=1;i<=m;i++)
    {
        cin>>z>>y>>x;
        if(z==1)
        join(y,x);
        else
        if(find(y)==find(x))
        cout<<'Y'<<endl;
        else
        cout<<'N'<<endl;
    }
    return 0;
}

by 一念之间 @ 2017-07-16 20:28:17

#include<bits/stdc++.h>
using namespace std;
int f[10001],n,m,zi,xi,yi;
int getf(int x)
{
    if(f[x]==x) return x;//f[x]最后为根节点 
    else 
    {f[x]=getf(f[x]);//压缩路径，把路过的点付值，提高速度 
     return f[x]; 
     } 
}
void add(int x,int y)
{ int t1,t2;
    t1=getf(x);
    t2=getf(y);
    if(t1!=t2)
    f[t2]=t1;//如果不是同一祖先，t2合并到t1内 
    return; 
}
void ch(int x,int y)
{   int a1,a2;
    a1=getf(x);
    a2=getf(y);
    if(a1==a2) cout<<"Y"<<endl;
    else cout<<"N"<<endl;
}
int main()
{
  cin>>n>>m;
   for(int i=1;i<=n;i++)
   f[i]=i;
   for(int i=1;i<=m;i++)
   {
       cin>>zi>>xi>>yi;
       if(zi==1)
       add(xi,yi);
       if(zi==2)
       ch(xi,yi);
   }
}

by QRcode @ 2017-07-27 14:48:12

合并应该是x所在的并查集和y所在的并查集合并，是把一个root合并到另一个root上，不是直接fa[x]=y

by 早右昕 @ 2017-07-28 15:40:26

楼上说话一点用都没有

by wzhhahah @ 2017-08-04 16:43:58

每次询问都需要给出应答，但是你的最外层if中r1!=r2会减少一些应答

by wzhhahah @ 2017-08-04 16:45:14

不对是增多一些多余的应答