/ Vijos / 讨论 / 家族 /

就过了两个点,求大神解惑……

#include<iostream>

using namespace std;
const int MAXN=5011;
int a[MAXN];
int main(){
int i,n,m,p,x,y; int rele(int); cin>>n>>m>>p; for(i=1;i<=n;i++)a[i]=i; for(i=1;i<=m;i++){ cin>>x>>y; if(x>y)a[x]=a[y]; else a[y]=a[x]; } for(i=1;i<=p;i++){ cin>>x>>y; if(rele(x)==rele(y))cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
int rele(int x){
if(a[x]==x)return x; else return rele(a[x]); }

2 条评论

  • @ 2014-04-14 13:00:01

    你的并查集只改变了 当前关系 没有从父节点去改变关系

  • @ 2014-04-14 12:58:52

    3 2 1
    2 3
    1 3
    2 3
    这组数据你试一试 如果不出意外你的程序会输出NO 单色答案是YES
    2 3 关系处理完a[3]=2
    1 3 关系处理完a[3]=1

  • 1

信息

ID
1034
难度
4
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
9362
已通过
3838
通过率
41%
被复制
12
上传者