n,m,p=[int(i)for i in raw_input().split()]

s=[]
for i in range(0,n+1):
s.append([i,1])

def find(a):
while a!=s[a][0]:
s[a][0]=s[s[a][0]][0]
a=s[a][0]
return a

def link(a,b):
ar=find(a)
br=find(b)
if ar!=br:
if s[ar][1]<s[br][1]:
s[ar][0]=br
s[br][1]+=s[ar][1]
else:
s[br][0]=ar
s[ar][1]+=s[br][1]

for i in range(0,m):
x,y=[int(j)for j in raw_input().split()]
link(x,y)

for i in range(0,p):
x,y=[int(j)for j in raw_input().split()]
if find(x)==find(y):
print 'Yes'
else:
print 'No'

program org;
var
x,i,j,m,n,a,b,p:longint;
fa:array[1..5000] of longint;

function find(x:longint):longint;
begin
if x=fa[x] then exit(x);
fa[x]:=find(fa[x]);
exit(fa[x]);
end;
begin
read(n,m,p);
for i:=1 to n do fa[i]:=i;
for i:=1 to m do begin read(a,b);
fa[find(a)]:=find(b);
end;
for i:=1 to p do begin read(a,b);
if fa[a]=fa[b] then writeln('yes') else writeln('no');end;
for i:=1 to n do writeln(fa[i]);
end.

#include<iostream>
#include<string>
using namespace std;
int n,m,x,y,q,father[10000];
string s[5005];
int find(int x)
{
if(father[x]!=x) father[x]=find(father[x]);
return father[x];
}
void link(int x,int y)
{
father[y]=x;
}
int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
int l1=find(x);
int l2=find(y);
if(l1!=l2) link(l1,l2);
}
for(int i=1;i<=q;i++)
{
cin>>x>>y;
if(find(x)==find(y)) s[i]="Yes";
else
s[i]="No";
}
for(int i=1;i<=q;i++)
cout<<s[i]<<endl;
}

并查集，采用了路径压缩，可以阅读关于并查集的资料以帮助理解代码

Pascal Code

var
father:array[1..5000] of longint; //father数组存储顶点的上级之一
n,m,p,i,t1,t2:longint;
function find(x:longint):longint;
begin
if x=father[x] then exit(x);
father[x]:=find(father[x]); //路径压缩
exit(father[x]);
end;
procedure merge(x,y:longint);
begin
father[find(x)]:=find(y); //令y的父亲成为x的父亲的上级
end;
begin
readln(n,m,p);
for i:=1 to n do
father[i]:=i;
for i:=1 to m do
begin
readln(t1,t2);
merge(t1,t2);
end;
for i:=1 to p do
begin
readln(t1,t2);
if find(t1)=find(t2) then writeln('Yes')
else writeln('No');
end;
end.

哈，原来这就是并查集，看了下书就会啦，一遍AC，继续练去喽~
###Block code

program ex;
var fa:array[1..5000] of longint;
i,j,n,m,p,k1,k2:longint;
ans:string;
function father(x:longint):longint;
begin
if fa[x]=x then
exit(x);
fa[x]:=father(fa[x]); exit(fa[x]);
end;

procedure add(a,b:longint);
var f1,f2:longint;
begin
f1:=father(a); f2:=father(b); fa[f2]:=f1;
end;

function search(a1,a2:longint):string;
begin
if father(a1)=father(a2) then
exit('Yes')
else
exit('No');
end;

begin //main
read(n,m,p);
for i:=1 to n do fa[i]:=i;

for i:=1 to m do begin
read(k1,k2); add(k1,k2);
end;

for i:=1 to p do begin
read(k1,k2); ans:=search(k1,k2); writeln(ans);
end;

end.

var f:array[1..5010]of longint;
n,m,p:longint;
function father(v:longint):longint;
begin
if f[v]=v then exit(v);
f[v]:=father(f[v]);
exit(f[v]);
end;

procedure add(x,y:longint);
var fx,fy:longint;
begin
fx:=father(x);
fy:=father(y);
if fx<>fy then f[fx]:=fy;
end;

procedure init;
var i,j,x,y:longint;
begin
readln(n,m,p);
for i:=1 to n do f[i]:=i;
for i:=1 to m do
begin
readln(x,y);
add(x,y);
end;
for i:=1 to p do
begin
readln(x,y);
if father(x)=father(y) then writeln('Yes')
else
writeln('No');
end;
end;

begin
init;
end.

var i,j,n,m,p,a,b,l:longint;
x:array[0..6001] of longint;
gx:array[0..8000,0..8000] of boolean;
begin
readln(n,m,p);
for i:=1 to n do
for j:=1 to n do
gx[i,j]:=false;
for i:=1 to m do
begin
readln(a,b);
gx[a,b]:=true;
gx[b,a]:=true;
end;
for i:=1 to n do
x[i]:=i;
for l:=1 to 8 do
for i:=1 to n do
for j:=1 to n do
if (gx[i,j]) and (x[j]>x[i]) then
x[j]:=x[i]
else if (gx[i,j]) then x[i]:=x[j];
for i:=1 to p do
begin
readln(a,b);
if x[a]=x[b] then writeln('Yes')
else writeln('No');
end;
end.
为什么都用并查集？？

#include<iostream>
#include<cstdio>
using namespace std;
const int maxb=5005;
int numd,numb,numq;
int fa[maxb];
struct m
{
int x;

int y;
};m k[maxb];
int get(int x)
{
int root=x;
while(root!=fa[root])
root=fa[root];
while(x!=root)
{
int tfa=fa[x];
fa[x]=root;
x=tfa;

}
return root;

}
int main()
{
int a,b;
scanf("%d%d%d",&numd,&numb,&numq);

for(int i=1;i<=numd;i++)
fa[i]=i;
for(int i=1;i<=numb;i++)
{
scanf("%d%d",&k[i].x,&k[i].y);

fa[get(k[i].x)]=get(k[i].y);
}
for(int i=1;i<=numq;i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(get(a)==get(b))
printf("Yes\n");
else
printf("No\n");
}

return 0;

}
没看清大小写。。。

var
a:array[1..5000]of longint;
s:array[1..5000]of string;
m,n,p,i,x,y:longint;
function findfather(x:longint):longint;
begin
if a[x]<>x then
findfather:=findfather(a[x])
else
findfather:=a[x];
end;
begin
readln(n,m,p);
for i:=1 to n do
a[i]:=i;
for i:=1 to m do
begin
readln(x,y);
x:=findfather(x);
a[x]:=findfather(y);
end;
for i:=1 to n do
a[i]:=findfather(i);
for i:=1 to p do
begin
readln(x,y);
if a[x]<>a[y] then
s[i]:='No'
else
s[i]:='Yes';
end;
for i:=1 to p do
writeln(s[i]);
end.

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 828 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 832 KiB, score = 10
测试数据 #6: Accepted, time = 7 ms, mem = 828 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 832 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 832 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 832 KiB, score = 10
Accepted, time = 67 ms, mem = 832 KiB, score = 100
####代码
program family;
var
father:array[1..5000] of integer;
n,m,p,i,a,b:integer;
function getfather(v:integer):integer;
begin
if father[v]=v then exit(v);
father[v]:=getfather(father[v]);
getfather:=father[v];
end;
procedure merge(x,y:integer);
begin
x:=getfather(x);
y:=getfather(y);
father[x]:=y;
end;
function judge(x,y:integer):boolean;
begin
x:=getfather(x);
y:=getfather(y);
exit(x=y);
end;
begin
readln(n,m,p);
for i:=1 to n do father[i]:=i;
for i:=1 to m do
begin
readln(a,b);
if not judge(a,b) then merge(a,b);
end;
for i:=1 to p do
begin
readln(a,b);
if judge(a,b) then writeln('Yes') else writeln('No');
end;
readln;
end.
并查集。
一定要审题！注意**大小写**！

P1034 家族
解题报告：
很明显这道题用到的是并查集，而且是并查集的模板题。
不需要任何变化，。首先使每个人形成一个独立的集合；
对于读入的m对关系，查询他们是否属于一个集合，不属于就合并；
对于读入的p个查询x，y，只要判断find（x）== f ind（y）？；
如果等于就输出“Yes”， 反之输出“No”即可。

#include<iostream>
using namespace std;
int f[5001];
int find(int x)
{
if(f[x]!=x)
f[x]=find(f[x]);
return f[x];
}
main()
{
int n,m,p,i,x,y,a,b;
cin>>n>>m>>p;
for(i=1;i<=n;i++)
f[i]=i;
for(i=1;i<=m;i++)
{
cin>>x>>y;
a=find(x);
b=find(y);
if(a!=b)
f[b]=a;
}
for(i=1;i<=p;i++)
{
cin>>x>>y;
if(find(x)==find(y))
cout<<"Yes\n";
else
cout<<"No\n";
}
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 512 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 512 KiB, score = 10
测试数据 #6: Accepted, time = 7 ms, mem = 512 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 516 KiB, score = 10
测试数据 #8: Accepted, time = 7 ms, mem = 516 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 516 KiB, score = 10
Accepted, time = 29 ms, mem = 516 KiB, score = 100

#include<cstdio>
using namespace std;
int n,m,p,parent[5005],fam[5000];
int find(int x)
{
if(parent[x]==x) return x;
parent[x]=find(parent[x]);
return parent[x];
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++){
parent[i]=i;
}
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
int a1=find(a),b1=find(b);
parent[a1]=b1;
}
for(int i=1;i<=p;i++){
int c1,c2;
scanf("%d%d",&c1,&c2);
if ( find(c1)==find(c2) ) printf("Yes\n");else printf("No\n");
}
return 0;
}

#include<cstdio>
int n,m,p;
int id[5002]={0};
inline void link(int x,int y);
inline int find(int x);
int main(){
scanf("%d %d %d\n",&n,&m,&p);
for(int i=1;i<=n;i++)id[i]=i;
for(int i=0;i<m;i++){
int x,y;
scanf("%d %d\n",&x,&y);
link(x,y);
}
for(int i=0;i<p;i++){
int x,y;
scanf("%d %d\n",&x,&y);
if(find(x)==find(y)){
printf("Yes\n");
}else printf("No\n");
}
}
inline void link(int x,int y){
int xroot=find(x),yroot=find(y);
id[yroot]=xroot;
}
inline int find(int x){
while(id[x]!=x){
x=id[x];
}
return x;
}
写得有点丑，没加路径压缩，用了75ms，压缩后更快

就过了两个点，求大神解惑……
#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]);
}

弱弱的题目，最简单的并查集，代码略丑，望请原谅
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=5001;
int t[N],n,m,p,i;
int findR(int x){
if(t[x]==-1)return x;
else return findR(t[x]);
}
void mergeR(int x,int y){
int X=findR(x);
int Y=findR(y);
if(X!=Y)t[X]=Y;
}
void findans(int x,int y){
int X=findR(x);
int Y=findR(y);
if(X!=Y)printf("No\n");
else printf("Yes\n");
}
int main(){
cin>>n>>m>>p;
memset(t,-1,sizeof(t));
for(i=1;i<=m;i++){
int x1,x2;
scanf("%d %d",&x1,&x2);
mergeR(x1,x2);
}
for(i=1;i<=p;i++){
int x1,x2;
scanf("%d %d",&x1,&x2);
findans(x1,x2);
}
return 0;
}

#include<iostream>
#include<cstdio>
using namespace std;
int father[50002],a,b,m,n,p;
int find(int x)
{

if (!father[x]) return x;
father[x]=find(father[x]);

return father[x];
}
int main()
{

cin>>n>>m>>p;

for (int i=1;i<=m;i++)
{

cin>>a>>b;

a=find(a);
b=find(b);
father[a]=b;

}

for(int i=1;i<=p;i++)
{

cin>>a>>b;

a=find(a);b=find(b);

if(a==b)printf("Yes");else printf("No");

}

return 0;
}

标准并查集，啥也不说了，很简单的程序
#include <cstdio>
using namespace std;
int m,n,p;
int R[5001]={0};
int find(int t)
{
if(!R[t]) return t;
else return R[t] = find(R[t]);
}
int main()
{
scanf("%d %d %d",&n,&m,&p);
int a,b,x,y;
for(int i = 0;i < m;i ++)
{
scanf("%d %d",&a,&b);
x = find(a);
y = find(b);
if(x != y) R[x] = y;
}

for(int i = 0;i < p;i ++)
{
scanf("%d %d",&a,&b);
x = find(a);
y = find(b);
printf("%s",(x == y) ? "Yes\n" : "No\n");
}
return 0;
}

Vijos题解：http://user.qzone.qq.com/616674147/2

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步