社會(huì)關(guān)系網(wǎng)絡(luò)

比賽描述

現(xiàn)代社會(huì)通信便捷，借助于Internet形成了各式各樣的社區(qū)，每個(gè)人都可能屬于多個(gè)社交圈，尤其是Facebook類社交網(wǎng)站的出現(xiàn)，使世界縮小了，人與人的交往擴(kuò)大了頻繁了。sed同學(xué)正在做這方面的畢業(yè)設(shè)計(jì)課題，指導(dǎo)老師給他布置了一個(gè)任務(wù)：已知一群人的社會(huì)關(guān)系網(wǎng)絡(luò)，判斷兩個(gè)人之間的關(guān)系，他們是否可以通過社交圈的人相互結(jié)識(shí)。

輸入

第一行包括三個(gè)整數(shù)：n、 m、k，分別表示人數(shù)、社區(qū)數(shù)、查詢兩個(gè)人之間的關(guān)系的用例數(shù) (1 ≤ n ≤ 10000, 0 ≤ m ≤ 100，1 ≤ k≤ 100)。

m行，每行首先給出一個(gè)社區(qū)的人數(shù)，然后給出代表人的序號(hào)。

k行，每行給出待查詢的兩個(gè)人（用序號(hào)表示）。

輸出

   輸出k行，每行給出兩個(gè)人（用序號(hào)表示）、YES或NO， YES表示這兩個(gè)人可以通過社交圈的人相互結(jié)識(shí)，NO表示不能。

注意：輸出部分的結(jié)尾要求包含一個(gè)多余的空行。

樣例輸入

3 1 22 1 20 11 2

樣例輸出

0 1 NO1 2 YES  

    此題是一道典型的使用并查集解決的問題。之前了解過并查集結(jié)構(gòu)，通過此題練手以達(dá)到算法訓(xùn)練效果。

    在此給出AC源碼：

#include<stdio.h>const int maxn=10005;int PRe[maxn];int find(int x)                                        //查找根節(jié)點(diǎn){	int r=x;	while (pre[r]!=r)              //返回根節(jié)點(diǎn) r		r=pre[r];	int i=x,j ;	while( i != r )                  //路徑壓縮	{		j=pre[i]; // 在改變上級(jí)之前用臨時(shí)變量  j 記錄下他的值		pre[i]=r ; //把上級(jí)改為根節(jié)點(diǎn)		i=j;	}	return r ;}void join(int x,int y)             //判斷x y是否連通，//如果已經(jīng)連通，就不用管了 //如果不連通，就把它們所在的連通分支合并起,{	int fx=find(x),fy=find(y);	if(fx!=fy)		pre[fx]=fy;}int main(){	int n,m,k;	while(~scanf("%d%d%d",&n,&m,&k))	{		for(int i=0; i<n; i++)			pre[i]=i;        //初始化		for(int i=0; i<m; i++)		{			int num,first,next;			scanf("%d",&num);			if(num==0||num==1)				continue;			scanf("%d",&first);			for(int i=1; i<num; i++)			{				scanf("%d",&next);				join(first,next);			}		}		while(k--)//查詢		{			int a,b;			scanf("%d%d",&a,&b);			if(find(a)==find(b))				printf("%d %d YES/n",a,b);			else				printf("%d %d NO/n",a,b);		}	}}