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

P1034家族
Accepted
记录信息
评测状态 Accepted
题目 P1034 家族
递交时间 2013-12-21 22:13:55
代码语言 C++
评测机 VijosEx
消耗时间 559 ms
消耗内存 484 KiB
评测时间 2013-12-21 22:13:57
评测结果

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 484 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 476 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 484 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 484 KiB, score = 10

测试数据 #4: Accepted, time = 31 ms, mem = 480 KiB, score = 10

测试数据 #5: Accepted, time = 31 ms, mem = 480 KiB, score = 10

测试数据 #6: Accepted, time = 93 ms, mem = 480 KiB, score = 10

测试数据 #7: Accepted, time = 109 ms, mem = 480 KiB, score = 10

测试数据 #8: Accepted, time = 125 ms, mem = 480 KiB, score = 10

测试数据 #9: Accepted, time = 140 ms, mem = 480 KiB, score = 10

Accepted, time = 559 ms, mem = 484 KiB, score = 100
代码

/*
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

Yes
Yes
No
*/
#include<iostream>
using namespace std;

/*合并两个不相交集合
操作很简单：先设置一个数组Father[x]，表示x的“父亲”的编号。
那么，合并两个不相交集合的方法就是，找到其中一个集合最父亲的父亲（也就是最久远的祖先），将另外一个集合的最久远的祖先的父亲指向它。
*/
const int MAX = 5000;

int get_father(int faher[], const int size, int x);
void Union(int father[], const int size, int x, int y);

int main(void)
{
int father[MAX + 5];
int n, m, p;
cin >> n >> m >> p;
for (int i = 0; i < n + 1; i++)
{
father[i] = i;
}
int people_a, people_b;
for (int i = 0; i < m; i++)
{
cin >> people_a >> people_b;
Union(father, MAX + 5, people_a, people_b);
}
for (int i = 0; i < p; i++)
{
cin >> people_a >> people_b;
if (get_father(father, MAX + 5, people_a) == get_father(father, MAX + 5, people_b))
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
return 0;
}

void Union(int father[], const int size, int x, int y)
{
int fx = get_father(father, size, x);
int fy = get_father(father, size, y);
if (fx != fy)
{
father[fx] = fy;
}
}

int get_father(int father[], const int size, int x)
{
if (father[x] == x)
return x;
else
return get_father(father, size, father[x]);
}

并查集秒过
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,q;
int a,b,c,d;
int f[5005],deep[5005];
int find(int x)
{
if(f[x]!=x)f[x]=find(f[x]);
return f[x];
}
void hebing(int x,int y)
{
int i=find(x);
int j=find(y);
if(i==j)return ;
else if(deep[i]>=deep[j])
{
deep[i]+=deep[j];
f[j]=i;

}
else
{
deep[j]+=deep[i];
f[i]=j;

}
}

int main()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
f[i]=i,deep[i]=1;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
hebing(a,b);
}
for(int i=1;i<=q;i++)
{
cin>>c>>d;
if(find(c)==find(d))
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

return 0;
}

第一次写并查集，参考了一下大神的代码
代码
#include <iostream>
#include <string>
using namespace std;
#define MAX 5000
int father[MAX];
// 初始化
void Make_set(int x)
{
father[x]=x;
}
// 查找 father
int Find_set(int x)
{
if(x!=father[x])
{
father[x]=Find_set(father[x]);
}
return father[x];
}
// 合并 x,y在一个集合里
int Union_set(int x,int y)
{
x=Find_set(x);
y=Find_set(y);
if(x==y) // 相等说明在同一集合里
{
return 0;
}
else //不相等 将x的father改为y的father，使x，y在同一集合里
father[y]=x;
}
int main()
{
int n,m,p,i,a,b;

cin>>n>>m>>p;
// 初始化
for(i=1;i<=n;i++)
Make_set(i);
// 合并 集合
for(i=1;i<=m;i++)
{
cin>>a>>b;
Union_set(a,b);
}
// 查找是否是在同一集合里
while(p--)
{
cin>>a>>b;
if(Find_set(a)==Find_set(b))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}

并查集模板题……不知为什么n久以前的其他思路都过不了……

#include <cstdio>
#include <cstring>
#include <algorithm>

int n, m, p;
#define REP( i, n ) for ( int i = 1; i <= n; i ++ )
#define FOR( i, a, b ) for ( int i = a; i <= b; i ++ )
#define DWN( i, a, b ) for ( int i = b; i >= a; i -- )
#define RST( a, x ) memset ( a, x, sizeof ( a ) );
#define ONLINE_JUDGE NULL
#define DISJOINT_SET_USED NULL
#define NSIZE 6000

#ifdef DISJOINT_SET_USED

#ifndef FX
#define FX father
#endif
#ifndef GFX
#define GFX( x ) GetFather ( x )
#endif

int father[ NSIZE ];
void SetFather ();
int GetFather ( int x );
void SetFather ()
{
REP ( i, n ) FX[ i ] = i;
}
int GetFather ( int x )
{
if ( FX[ x ] != x ) FX[ x ] = GetFather ( FX[ x ] );
return FX[ x ];
}

#endif

using namespace std;
char out[ 2 ][ 10 ] = { "No", "Yes" };
int main ()
{

#ifndef ONLINE_JUDGE
freopen ( "P1034.in", "r", stdin );
freopen ( "P1034.out", "w", stdout );
#endif

int t1, t2;
scanf ( "%d%d%d", &n, &m, &p );
SetFather ();
REP ( i, m )
{
scanf ( "%d%d", &t1, &t2 );
if ( GFX ( t1 ) != GFX ( t2 ) ) FX[ FX[ t1 ] ] = FX[ t2 ];
}
REP ( i, p )
{
scanf ( "%d%d", &t1, &t2 );
printf ( "%s\n", out[ GFX ( t1 ) == GFX ( t2 ) ] );
}
return 0;
}

var f:array[0..5001] of longint; n,m,i,p,a,b,f1,f2:longint;
Function fa(d:longint):longint;
var i:longint;
begin
if f[d]=d then exit(d);
f[d]:=fa(f[d]);fa:=f[d];
end;
begin
readln(n,m,p);
for i:=1 to n do f[i]:=i;
for i:=1 to m do begin
readln(a,b); f1:=fa(a);
f2:=fa(b); f[f1]:=f2; end;
for i:=1 to p do begin
readln(a,b); f1:=fa(a); f2:=fa(b);
if f1=f2 then writeln('Yes') else writeln('No');
end;
end.

并查集的算法
var i,j,k,l,n,m,x,y,p:longint;
father:array[0..10000] of longint;

function getfather(u:longint):longint;
begin
if father[u]=u then exit(u)
else father[u]:=getfather(father[u]);
exit(father[u]);
end;

procedure union(u,v:longint);
var fu,fv:longint;
begin
fu:=getfather(u);
fv:=getfather(v);
if fu<>fv then father[fu]:=fv;
end;

begin
readln(n,m,p);
for i:=1 to n do father[i]:=i;
for i:=1 to m do begin
read(x,y);
if getfather(x)<>getfather(y) then union(x,y);
end;
for i:=1 to p do begin
read(x,y);
if getfather(x)<>getfather(y) then writeln('No')
else writeln('Yes');
end;
end.

var
f:array[1..5000]of integer;
m,n,p,x,y,x1,y1:integer;
j:longint;

function find(i:integer):integer;
begin
if f[i]=i then exit(i);
f[i]:=find(f[i]);
exit(f[i]);
end;

BEGIN
readln(n,m,p);
for j:=1 to n do f[j]:=j;
for j:=1 to m do
begin
readln(x,y);
x1:=find(x);
y1:=find(y);
if x1<>y1 then f[x1]:=y1;
end;
for j:= 1 to p do
begin
readln(x,y);
x1:=find(x);
y1:=find(y);
if x1=y1 then writeln('Yes')
else writeln('No');
end;
end.

//代码有点长，可以简化

坑死爹了
调了两个小时的wrong answer
原来还要加**"\n"**

点击查看程序源码+详细题解

编译通过...

├ 测试数据 01：答案正确... (0ms, 692KB)

├ 测试数据 02：答案正确... (0ms, 692KB)

├ 测试数据 03：答案正确... (0ms, 692KB)

├ 测试数据 04：答案正确... (0ms, 692KB)

├ 测试数据 05：答案正确... (0ms, 692KB)

├ 测试数据 06：答案正确... (0ms, 692KB)

├ 测试数据 07：答案正确... (0ms, 692KB)

├ 测试数据 08：答案正确... (0ms, 692KB)

├ 测试数据 09：答案正确... (0ms, 692KB)

├ 测试数据 10：答案正确... (0ms, 692KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 3ms / 692KB

var

n,m,p,a,mi,mj,d:integer;

e:array[1..5000]of integer;

h:array[1..5000,1..5000]of integer;

begin

read(n,m,p);

for a:=1 to m do begin

read(mi,mj); if (mi>=1)and(mj

算法：并查集

点击查看代码

规模较弱，Floodfill/并查集均可..首先Floodfill的咱果然是个奇葩么0.0

并查集

注意合并a,b的时候一定要让a的树根指向b的树根，否则会WA

样例数据即使在你写错（上面那个地方）的情况下答案也是一样的

#include

const int maxn=5005;

int p[maxn];

int find(int x)

{

return x==p[x]?x:p[x]=find(p[x]);

}

void Union(int x,int y)

{

x=find(x); y=find(y);

p[x]=y;

}

int main()

{

int n,m,q,i,x,y;

scanf("%d%d%d",&n,&m,&q);

for(i=1;i

var

a,b:array[1..5000]of integer;

i,j,k,n,m,x,y,p:integer;

function find(x:integer):integer;

begin

if xa[x] then a[x]:=find(a[x]);

find:=a[x];

end;

begin

readln(n,m,p);

for i:=1 to n do

begin

a[i]:=i; b[i]:=1;

end;

for i:=1 to m do

begin

readln(x,y);

x:=find(x); y:=find(y);

if xy then

if b[x]=b[y] then

begin

b[x]:=b[x]+1; a[y]:=x;

end

else if b[x]>b[y] then a[y]:=x

else a[x]:=y;

end;

for i:=1 to p do

begin

readln(x,y);

if find(x)=find(y) then writeln('Yes')

else writeln('No');

end;

end.

var

i1,i2,i,m,n,p,p1,q:longint;

father:array[1..5000]of integer;

function find(kk:longint):longint;

var j:longint;

begin

j:=kk;

while father[j]0 do j:=father[j];

find:=j;

end;

begin

read(n,m,p);

fillchar(father,sizeof(father),0);

for i:=1 to m do

begin

read(i1,i2);

p1:=find(i1);

q:=find(i2);

if p1q then father[q]:=p1;

end;

for i:=1 to p do

begin

read(i1,i2);

p1:=find(i1);

q:=find(i2);

if (p1=0)or(q=0)or(p1=q) then writeln('Yes')

else writeln('No');

end;

end.

Program relative;

var

x,y,n,m,p,i,a,b:longint;

father:array[1..5000] of longint;

function find(i:longint):longint;

begin

if father[i]=0 then exit(i);

father[i]:=find(father[i]);

exit(father[i]);

end;{find}

Begin

fillchar(father,sizeof(father),0);

readln(n,m,p);//读入初始数据；

for i:=1 to m do//｛处理亲缘关系｝

begin

readln(a,b);

x:=find(a);

y:=find(b);

if xy then father[x]:=y;//判断a,b根节点是否相同，不同则加入亲戚系统；

end;{for}

for i:=1 to p do

begin

readln(a,b);

if find(a)=find(b) then writeln('Yes') else writeln('No');//询问a,b是否是亲戚；

end;{for}

End.{main}