/ Vijos / 讨论 / 家族 /

原来自己是自己的亲戚……

#include<iostream>
using namespace std;
#include<cstdio>

bool connect(int re[][5010],int have[],int k,int t,bool search[])
{
for(int i=0;i<have[k];i++)
if(!search[re[k][i]])
{
search[re[k][i]]=true;
if(re[k][i]==t)return true;
else
if(connect(re,have,re[k][i],t,search))
return true;
}
return false;
}

int re[5010][5010]={0};
int have[5010]={0};
int main()
{
int n,m,p;
cin>>n>>m>>p;
for(int i=0;i<m;i++)
{
int k,t;
scanf("%d %d",&k,&t);
re[k][have[k]]=t;
re[t][have[t]]=k;
have[k]++;
have[t]++;
}
for(int i=0;i<p;i++)
{
int k,t;
scanf("%d %d",&k,&t);
if(k==t)
{
cout<<"Yes"<<endl;
continue;
}
bool search[5010]={0};
if(connect(re,have,k,t,search))cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}

3 条评论

  • @ 2016-03-16 16:17:45
    // input code here
    
  • @ 2016-03-13 14:31:32

    多谢提醒
    我终于对了……
    我终于对了……
    我终于对了……(重要的事情说三遍)

  • @ 2016-02-03 10:46:35

    如果存在x和y是亲戚,那么y和x是亲戚,所以x和x是亲戚哈哈哈哈哈哈

  • 1

信息

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