题解 - Vijos

0

wb6291415 LV 4 @ 2010-04-08 22:59:25

#include

#define maxn 100

using namespace std;

typedef struct node

{

int data;

int rank;

int parent;

}UFStree;

UFStree t[maxn];

void Make_Set(int n) //定点编号1—n

{

int i;

for(i=1;it[y].rank)

t[y].parent=x;

else

{

t[x].parent=y;

if(t[x].parent==t[y].parent)

t[y].rank++;

}

}

int main()

{

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

cin>>n>>m>>p;

int answer[maxn];

memset(answer,0,sizeof(answer));

Make_Set(n);

for(i=1;i>x>>y;

Union(x,y);

}

for(i=1;i>x>>y;

if(Find_Set(x)==Find_Set(y)) answer[i]=1;

}

for(i=1;i

0

hannett1 LV 7 @ 2010-04-01 18:32:46

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 56ms

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

Accepted 有效得分：100 有效耗时：65ms

#include

#include

#include

#include

#include

using namespace std;

#define ANS_Yes puts("Yes")

#define ANS_No puts("No" )

#define MS(s) memset(s,0,sizeof(s))

int n,m,q,fa[5000];

int find(int x) {

if( fa[x]==x )

return x;

fa[x]=find(fa[x]);

return fa[x];

}

int main() {

cin >>n >>m >>q;

MS(fa);

int a,b;

for(int i=1;ia >>b;

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

}

for(int i=1;i>a >>b;

if(find(a)==find(b))

ANS_Yes;

else

ANS_No;

}

return 0;

}

0

sza603 LV 6 @ 2009-11-19 21:24:33

#include

int rep[5001];

#define Make_Set(i) (rep[i]=(i))

int Find(int i) {

if(rep[i]==i) return i;

return rep[i]=Find(rep[i]);

}

#define Union(i,j) (rep[Find(i)]=Find(j))

int main(void) {

int n,m,p,i,a,b;

static const char*yesno[2]={"No","Yes"};

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

for(i=0;i

0

328705509 LV 7 @ 2009-11-18 19:47:10

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

Accepted 有效得分：100 有效耗时：0ms

水题~~~无耻的秒了~~~~~

var s:array[1..10000] of longint;

n,m,q,i,j,k,a,b,x:longint;

function find(x:longint):longint;

begin

while s[x]>=0 do x:=s[x];

find:=x;

end;

procedure short(i:longint);

begin

if s[i]s then begin

s:=s[a]+s;

s[a]:=b;

end else begin

s[a]:=s[a]+s;

s:=a;

end;

end;

for i:=1 to q do begin

readln(j,k);

if find(j)=find(k) then writeln('Yes') else writeln('No');

end;

end.

0

hy98 LV 7 @ 2009-11-11 18:44:43

累死了！才过

0

我马 LV 7 @ 2009-11-10 20:07:29

const maxsize=5000;

var a:array[1..maxsize] of longint;

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

function find_set(x:longint):longint;

begin

if a[x]=x then exit(x)

else

begin

find_set:=find_set(a[x]);

a[x]:=find_set;

end;

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);

a[find_set(x)]:=find_set(y);

end;

for i:=1 to p do

begin

readln(x,y);

if a[find_set(x)]=a[find_set(y)] then writeln('Yes')

else writeln('No');

end;

end.

0

hzr hzr LV 7 @ 2009-11-02 20:33:53

var

d,m,n,i,j,mm,nn:longint;

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

function find(x:longint):longint;

begin

if f[x]=x then exit(f[x]) else

begin

f[x]:=find(f[x]);

exit(f[x]);

end;

end;

procedure hebin(p,q:longint);

var

aa,bb:longint;

begin

aa:=find(p);

bb:=find(q);

f[aa]:=bb;

end;

procedure init;

var a,b,c:longint;

begin

read(a,b,c);

for i:=1 to a do f[i]:=i;

for i:=1 to b do

begin

read(m,n);

hebin(m,n);

end;

for j:=1 to c do

begin

read(mm,nn);

if find(mm)=find(nn) then write('Yes') else write('No');

end;

end;

begin

init;

end.

标准的并查集。。。

0

andyzero LV 4 @ 2009-10-30 16:58:29

我用路径压缩可以0MS的,怎么楼下有几百MS

0

小治 LV 8 @ 2009-10-30 10:09:21

验证码:0RP5

……

呃……还是AC了

这种验证码纪念一下并查集啊……

0

冬天不冷 LV 8 @ 2009-10-27 13:59:53

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

Accepted 有效得分：100 有效耗时：0ms

program ex;

var n,m,p,a,b,i:longint;

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

function getfather(v:longint):longint;

begin

if father[v]=v then exit(v);

father[v]:=getfather(father[v]);

getfather:=father[v];

end;

procedure mg(x,y:longint);

begin

father[x]:=getfather(father[x]);

father[y]:=getfather(father[y]);

father[father[x]]:=father[y];

end;

function try(x,y:longint):boolean;

begin

if getfather(father[x])=getfather(father[y]) then exit(true) else exit(false);

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);

mg(a,b);

end;

for i:=1 to p do

begin

readln(a,b);

if try(a,b) then writeln('Yes') else writeln('No');

end;

end.

0

Lebron James LV 8 @ 2009-10-27 19:01:21

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

Accepted 有效得分：100 有效耗时：0ms

program P1034;

var n,i,m,p,z,w:longint;

x,y,f:array [1..6000] of longint;

function find(x1:longint):longint;

var j:longint;

begin

if f[x1]=x1 then find:=x1

else find:=find(f[x1]);

f[x1]:=find;

end;

function pd(a,b:longint):string;

begin

if find(a)=find(b) then pd:='Yes'

else pd:='No';

end;

procedure hb(a,b:longint);

begin

if pd(a,b)='No' then f[find(a)]:=find(b);

end;

begin

readln(n,m,p);

for i:=1 to n do

f[i]:=i;

for i:=1 to m do

begin

readln(z,w);

hb(z,w);

end;

for i:=1 to p do

begin

readln(z,w);

writeln(pd(z,w));

end;

end.

0

lucky1 LV 8 @ 2009-10-24 22:58:00

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 88ms

├ 测试数据 08：答案正确... 212ms

├ 测试数据 09：答案正确... 275ms

├ 测试数据 10：答案正确... 244ms

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

Accepted 有效得分：100 有效耗时：819ms

经典的并查集入门题

千万别当做图论！

#include

using namespace std;

int s[5001],n,m,p,a,b;

int find(int x)

{

if(s[x]==-1)

return x;

else

return s[x]=find(s[x]);

}

int init()

{

int x1,y1,i;

cin>>n>>m>>p;

for(i=0;ia>>b;

x1=find(a);

y1=find(b);

if(x1!=y1)

s[x1]=y1;

}

}

int main(void)

{

init();

int x,y,i;

for(i=1;i>a>>b;

x=find(a);

y=find(b);

if(x==y)

cout

0

xiaowu2008 LV 8 @ 2009-10-21 22:28:09

陈阳啊，并查集写得好，不一定是用C++的啊，况且，蒋子彦还在你前面做好

0

陈阳11 LV 8 @ 2009-10-20 22:17:14

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 103ms

├ 测试数据 09：答案正确... 150ms

├ 测试数据 10：答案正确... 197ms

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

Accepted 有效得分：100 有效耗时：491ms

#include

#include

using namespace std;

int a[5100];

int n,m,p;

int findd(int x)

{

if (a[x]==0)

return x;

return a[x]=findd(a[x]);

}

int main ()

{

string xx[5001];

int i,j;

cin>>n>>m>>p;

int i1,j1;

for (i=1;i>i1>>j1;

if (findd(i1)!=findd(j1))

a[findd(j1)]=findd(i1);

}

for (i=1;i>i1>>j1;

if (findd(i1)==findd(j1))

xx[i]="Yes";

else

xx[i]="No";

}

for (i=1;i

0

neaolee LV 8 @ 2009-10-04 11:24:14

看来大家都把这道题当做自己练习并查集的第一道题啊呵呵

楼上jiamomo童鞋的讲解非常好，大家可以去看一下

顺便附上并查集核心代码：

1）合并两个不相交集合

Procedure Union(x,y:integer);{其中GetFather是下面将讲到的操作}

var fx,fy : integer;

begin

fx := GetFather(x);

fy := GetFather(y);

If fxfy then Father[fx] := fy;{指向最祖先的祖先}

end;

2）判断两个元素是否属于同一集合

Function Same(x,y:integer):boolean;

begin

if GetFather(x)=GetFather(y) then

exit(true) else

exit(false);

end;

并查集的优化

（1）路径压缩

Procedure Initialize;

var

i:integer;

begin

for i:=1 to maxv do

Father[i]:=i;

end;

Function GetFather(v:integer):integer;

begin

if Father[v]=v then

exit(v) else

Father[v]:=GetFather(Father[v]);

exit(Father[v]);

end;

（2）rank合并

合并时将元素少的集合合并到元素多的集合中。

function judge(x,y:integer):boolean;

var fx,fy : integer;

begin

fx := GetFather(x);

fy := GetFather(y);

If fx=fy then

exit(true) else

judge := false;

if rank[fx]>rank[fy] then

father[fy] := fx else begin

father[fx] := fy;

if rank[fx]=rank[fy] then

inc(rank[fy]);

end;

end;

初始化：fillchar(rank,sizeof(rank),0);

代码来自CSDN博客，转载请标明出处：http://blog.csdn.net/lewutian/archive/2009/07/19/4362182.aspx

菜鸟在大牛们的呵护下一步步成长

大家一定来帮帮咱们的vijos渡过难关，越来越好

0

chenye LV 8 @ 2009-10-02 16:56:52

并查集。。。用数组建立森林，a存父节点，h为记忆化数组以优化时间复杂度，存曾经的根 head求节点所在树的根

const maxn=5000;

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

a,h:array[1..maxn]of integer;

function head(x:integer):integer;

var xx:integer;

begin

xx:=h[x];

while xxa[xx] do xx:=a[xx];

head:=xx; h[x]:=xx;

end;

begin

readln(n,m,p);

for i:=1 to n do begin h[i]:=i; a[i]:=i; end;

for i:=1 to m do

begin

readln(x,y);

x:=head(x);

y:=head(y);

a[y]:=x;

end;

for i:=1 to p do

begin

readln(x,y);

x:=head(x); y:=head(y);

if x=y then writeln('Yes') else writeln('No');

end;

end.

0

song19931218 LV 9 @ 2009-09-20 08:25:53

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

program p1034;

var

fa,rank:array[1..10000] of integer;

n,m,p,a,b,i:integer;

procedure initial(n:integer);

var

i:integer;

begin

for i:=1 to n do fa[i]:=i;

fillchar(rank,sizeof(rank),0);

end;

function getfather(v:integer):integer;

begin

if fa[v]=v then exit(v)

else fa[v]:=getfather(fa[fa[v]]);

exit(fa[v]);

end;

function same(a,b:integer):boolean;

var

x,y:integer;

begin

x:=getfather(a); y:=getfather(b);

if x=y then exit(true) else exit(false);

end;

procedure union(a,b:integer);

var

x,y:integer;

begin

x:=getfather(a); y:=getfather(b);

if xy then

begin

if rank[x]>rank[y] then fa[y]:=x

else

begin

fa[x]:=y;

if rank[x]=rank[y] then inc(rank[y]);

end;

end;

end;

begin

read(n,m,p);

initial(n);

for i:=1 to m do

begin

read(a,b);

union(a,b);

end;

for i:=1 to p do

begin

read(a,b);

if same(a,b) then writeln('Yes') else writeln('No');

end;

end.

经典并查集，详情参见NOCOW

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

Accepted 有效得分：100 有效耗时：0ms

0

SDreaming LV 10 @ 2009-09-18 16:12:56

沙题留名..

0

mq01 LV 8 @ 2009-09-15 12:07:16

回芒果木瓜榴莲……

“if a[a[i]]=0 then exit(a[i]);”

这句话好像不要也行的……

好像而已……

0

芒果木瓜榴莲 LV 9 @ 2009-09-12 21:51:10

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

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

Accepted 有效得分：100 有效耗时：0ms

突然发现了并查集的惊天秘密……

const filename='p1034';

var

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

i,j,n,m,p,x,y,z1,z2:longint;

function find(i:longint):longint;

begin

if a[i]=0 then exit(i); {

题解

282 条题解

家族

信息

状态

开发

支持

题解

282 条题解

家族

信息

状态

开发

支持

还没有账户？

登录