1075-社会关系网络
描述
现代社会通信便捷，借助于Internet形成了各式各样的社区，每个人都可能属于多个社交圈，尤其是Facebook类社交网站的出现，使世界缩小了，人与人的交往扩大了频繁了。sed同学正在做这方面的毕业设计课题，指导老师给他布置了一个任务：已知一群人的社会关系网络，判断两个人之间的关系，他们是否可以通过社交圈的人相互结识。
输入
第一行包括三个整数：n、 m、k，分别表示人数、社区数、查询两个人之间的关系的用例数 (1 ≤ n ≤ 10000, 0 ≤ m ≤ 100，1 ≤ k ≤ 100)。
m行，每行首先给出一个社区的人数，然后给出代表人的序号。
k行，每行给出待查询的两个人（用序号表示）。
输出
输出k行，每行给出两个人（用序号表示）、YES或NO， YES表示这两个人可以通过社交圈的人相互结识，NO表示不能。
注意：输出部分的结尾要求包含一个多余的空行。
样例输入
3 1 2
2 1 2
0 1
1 2
样例输出
0 1 NO
1 2 YES
#include
#define maxn 10005
using namespace std;int P[maxn];
int N,M,k,a,b,n;int find(int i)
{int r,l,t;for(r=i;P[r]>=0;r=P[r]);if(i!=r){for(t=i;P[t]!=r;t=l){l=P[t];P[t]=r;}}return r;
}void union1(int x,int y)
{int temp=P[x]+P[y];if(P[x]>=P[y]){P[x]=y;P[y]=temp;}else{P[y]=x;P[x]=temp;}
}
int main()
{while(scanf("%d%d%d",&N,&M,&k)!=EOF){memset(P,-1,sizeof(P));while(M--){scanf("%d",&n);scanf("%d",&a);n--;while(n--){scanf("%d",&b);if(find(b)!=find(a))union1(find(b),find(a));}}while(k--){scanf("%d%d",&a,&b);if(find(a)==find(b))cout<
转载于:https://www.cnblogs.com/Rosanna/p/3436849.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！