该死的，自己和自己也算亲戚，crying~~~

下面是我的代码，貌似和其他人的不太一样呵呵，用的是C或者C++

#include

int a[5001];

int main()

{

int n,m,p,i,k,j,x,t,s;

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

for(k=0;k

编译通过...

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

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

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

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

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

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

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

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

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

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

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

program skjl;

begin

randomize;

if random(2)+1=1 then writeln('Yes')

else writeln('No');

end.

program p1034;

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

f:array[1..6001] of integer;

procedure un(n:integer);

begin

for i:=1 to n do

f[i]:=i;

end;

function getfather(i:integer):integer;

begin

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

begin

f[i]:=getfather(f[i]);

exit(f[i]);

end;

end;

procedure union(x,y:integer);

begin

if getfather(x)getfather(y) then f[getfather(x)]:=getfather(y);

end;

begin

readln(n,m,p);

un(n);

for i:=1 to m do

begin

readln(x,y);

union(x,y);

end;

for k:=1 to p do

begin

readln(x,y);

if getfather(x)=getfather(y) then writeln('Yes') else

writeln('No');

end;

end.

数组做的并查集,O(n)的复杂度

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

int n,m,p;

int a[5001][5001],top[5001];

int b[5001];

int main()

{

int i,j,x,y,tmp;

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

for(i=1;i

一次AC...被惊到

var

f,d:array [1..5000] of integer;

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

function find(xx:integer):integer;

var t:integer;

begin

t:=xx;

while f[t]t do t:=f[t];

exit(t);

end;

procedure union(xx,yy:integer);

var fx,fy:integer;

begin

fx:=find(xx);fy:=find(yy);

if d[fx]>d[fy] then f[fy]:=fx

else f[fx]:=fy;

if d[fx]=d[fy] then inc(d[fy]);

end;

begin

readln(n,m,p);

for i:=1 to n do begin

f[i]:=i;d[i]:=0;

end;

for i:=1 to m do begin

readln(x,y);

union(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.

错了

编译通过...

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

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

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

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 05：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 07：答案错误...程序输出比正确答案长

├ 测试数据 08：答案错误...程序输出比正确答案短

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：运行超时|格式错误...

为什么会这样??

下面是我的程序:

var k,a,b,i,ii,jj,n1,k1,m1,ans:longint;

a1,b1:array[1..50,1..50] of longint;

c:array[1..50] of boolean;

procedure mfh(i1:longint);

var j:longint;

begin

k:=k+1;

c[i1]:=true;

for j:=1 to n1 do

if (a1[i1,j]=1)and(c[j]=false) then

begin

b1[k1,k]:=j;

mfh(j);

end;

end;

begin

readln(n1,k1,m1);

for i:=1 to k1 do

begin

readln(a,b);

a1[a,a]:=1;

a1:=1;

a1[a,b]:=1;

a1:=1;

end;

k1:=1;

for i:=1 to n1 do

begin

k:=1;

if c[i]=false then

begin

b1[k1,k]:=i;

mfh(i);

k1:=k1+1;

end;

end;

for i:=1 to m1 do

begin

readln(a,b);

for ii:=1 to k1 do

begin ans:=0;

for jj:=1 to n1 do

if (b1[ii,jj]=a)or(b1[ii,jj]=b) then ans:=ans+1;

if ans=2 then begin writeln('Yes'); break; end

else if ii=k1 then writeln('No');

end;

end;

end.

给出我的程序，看似没有任何优化

//Vjios P1034 Relations

//Algorithm: Use array Rel to record A's Relations.

#include

using namespace std;

#define MAX 5020

int Rel[MAX];

int Fa ( int a ) {

int x = a;

while ( x != Rel[x]) {

x = Rel[x];

}

Rel[a] = x;

return x;

}

void Cha ( int a , int b) {

Rel[a] = Rel[Rel[a]] = Fa(b);

}

int main() {

int n, m, p;

cin >> n >> m >> p;

int i;

for ( i = 0; i < n; ++i) {

Rel[i] = i; }

int a, b;

for ( i = 0; i < m; ++i) {

cin >> a >> b;

if (Fa(a) != Fa(b)) Cha(a, b);

}

for ( i = 0; i < p; ++i) {

cin >> a >> b;

if (Fa(a) == Fa(b))

cout

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include "stdio.h"

int father[5001];

int find(int x)

{

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

else father[x]=find(father[x]);

return(find(father[x]));

}

int main()

{

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

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

for(i=1;i

Flag 　　 Accepted

题号 　　P1034

类型(?) 　　并查集

通过 　　3100人

提交 　　7855次

通过率 　　39%

难度 　　2

第3100个 庆祝下~

好简单 直接在提交里打的

var f:array[1..5000] of integer;

n,m,p,i,x,y,fx,fy:integer;

function findf(x:integer):integer;

begin

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

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

exit(f[x]);

end;

begin

readln(n,m,p);

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

for i:= 1 to m do

begin

readln(x,y);

fx:=findf(x);

fy:=findf(y);

f[fy]:=fx;

end;

for i:= 1 to p do

begin

readln(x,y);

fx:=findf(x);

fy:=findf(y);

if fx = fy then writeln('Yes')

else writeln('No');

end;

end.

var

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

a:array[1..1000]of integer;

begin

read(n,m,p);

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

for j:=1 to m do

begin

read(x,y);

t:=a[x];

a[x]:=y;

while a[y]a[x] do

y:=a[y];

a[y]:=t;

end;

for j:=1 to p do

begin

read(x,y);

t:=x;

while (a[x]y)and(a[x]t) do x:=a[x];

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

end;

end.

最最基本的并查集,连一丁点优化都不用的,嗖~就过了~

program sdfsdf;

var m,n,x,i,j,b,e,q:integer;

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

k:array[1..5000] of 0..1;

procedure makeset(a:integer);

begin

p[a]:=a;

//depth[a]:=0;

end;

function find(a:integer):integer;

begin

if a=p[a] then find:=a else find:=find(p[a]);

end;

procedure union(a,b:integer) ;

var fa,fb:integer;

begin

fa:=find(a); fb:=find(b) ;

p[fa]:=fb;

end;

begin

readln(n,m,x);

i:=0;b:=0;e:=0;

for i:=1 to n do makeset(i);

for i:=1 to m do

begin

readln(b,e);

union(b,e);

end;

for i:=1 to x do

begin

readln(b,e);

if find(b)=find(e) then begin inc(q); k[q]:=1; end else begin inc(q); k[q]:=0; end;

end;

for i:=1 to x do if k[i]=1 then writeln('Yes') else writeln('No');

end.

第3千个人过。。。

太好了 3000万岁 ~(≧▽≦)/~

const

maxn=6000;

var

n,m,p:longint;

i,j,k:longint;

tree:array[1..maxn] of longint;

function getfather(x:longint):longint;

begin

if tree[x]=x then exit(x);

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

getfather:=tree[x];

end;

procedure work;

begin

for i:=1 to p do

begin

readln(j,k);

if getfather(j)=getfather(k) then writeln('Yes')

else writeln('No');

end;

end;

procedure fil;

begin

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

end;

procedure init;

begin

readln(n,m,p);

fil;

for i:=1 to m do

begin

readln(j,k);

j:=getfather(j);

k:=getfather(k);

if jk then tree[k]:=j;

end;

end;

begin

init;

work;

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最后一组数据是不是特别大？

(不懂并查集，用了图的遍历,一次AC)

program P1034;

const maxn=5000;

type gtype=array[1..maxn,1..maxn] of boolean;

list=array[1..maxn] of longint;

var a:gtype;b:list;

n,m,p,i,j,k:longint;

function check:longint;

var i:longint;

begin i:=1;while (i

program vijos1034;

var

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

fa:array[0..10000] of longint;

function get(v:longint):longint;

begin

if fa[v]=v then get:=v

else

begin

fa[v]:=get(fa[v]);

get:=fa[v];

end;

end;

begin

readln(n,m,p);

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

for i:=1 to m do

begin

readln(x,y);

fx:=get(x);fy:=get(y);

fa[fy]:=fx;

end;

for i:=1 to p do

begin

readln(a,b);

fx:=get(a);

fy:=get(b);

if fx=fy then writeln('Yes') else writeln('No');

end;

end.

图的遍历也可以过....无向定义成有向结果爆了2次

program p1034;

var a:array[0..5000,0..5000] of byte;

t,d:array[1..5000] of integer;

z,y,i,j,k,n,m,p,kk:integer;

v:array[1..5000] of boolean;

procedure dfs(k:integer);

var i,j:integer;

begin

t[k]:=kk;

v[k]:=true;

for i:=1 to n do

if (v[i]=false) and (a[k,i]0)

then dfs(i);

end;

begin

readln(n,m,p);

fillchar (a,sizeof(a),0);

for i:=1 to m do

begin

readln(z,y);

a[z,y]:=1;

a[y,z]:=1;

end;

kk:=1;

for i:=1 to n do

if v[i]=false then

begin

dfs(i);

inc(kk);

end;

for i:=1 to p do

begin

readln(z,y);

if t[z]=t[y] then writeln('Yes')

else writeln('No');

end;

end.

标准的并查集~~~~

编译通过...

├ 测试数据 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 father:array [1..5001] of integer;

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

function find(a:integer):integer;

begin

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

else father[a]:=find(father[a]);

exit(find(father[a]));

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

a:=find(a);

b:=find(b);

if ab then father[a]:=b;

end;

for i:=1 to p do

begin

readln(a,b);

if find(a)=find(b) then writeln('Yes')

else writeln('No');

end;

end.

并查集原来如此简单.......（要加路径压缩）

标准并查集,直接写,原来并查集是如此简单...