第一次 一次AC！！！

FLODY 秒杀 通过foldy 解决传递的问题 再遍历一下 就可以了 感谢walala的报告

相传DFS和并查集也能做 下次试试

不过这个题的数据是一定有问题的，我的FOLDY 写的是a和b交流，b就一定和a 交流，结果AC了 应该注意一下这里

我拿 P1023的程序教上去秒杀........

P1022 和 P1023 怎么一样?

这个题居然一次DFS就能过……

汗……

数据太水了吧……

var

i,j,n,total:integer;

a:array[1..200,1..200]of integer;

b:array[1..200]of integer;

d:array[1..200]of boolean;

procedure dfs(k:integer);

var

i,j:integer;

begin

for i:=1 to b[k] do begin

if d[a[k,i]] then begin

d[a[k,i]]:=false;

dfs(a[k,i]);

end;

end;

end;

begin

readln(n);

total:=0;

for i:=1 to n do begin

j:=1;

read(a);

while a0 do begin

inc(j);read(a);

end;

b[i]:=j-1;

readln;

end;

fillchar(d,sizeof(d),true);

for i:=1 to n do begin

if d[i] then begin

d[i]:=false;

dfs(i);

inc(total);

end;

end;

writeln(total);

end.

var

i,j,n,total:integer;

a:array[1..200,1..200]of integer;

b:array[1..200]of integer;

d:array[1..200]of boolean;

procedure dfs(k:integer);

var

i,j:integer;

begin

for i:=1 to b[k] do begin

if d[a[k,i]] then begin

d[a[k,i]]:=false;

dfs(a[k,i]);

end;

end;

end;

begin

readln(n);

total:=0;

for i:=1 to n do begin

j:=1;

read(a);

while a0 do begin

inc(j);read(a);

end;

b[i]:=j-1;

readln;

end;

fillchar(d,sizeof(d),true);

for i:=1 to n do begin

if d[i] then begin

d[i]:=false;

dfs(i);

inc(total);

end;

end;

writeln(total);

end.

这道题可以用1023的代码AC!

效率O(n+m/10)

var

zz:array[1..40000] of record link,who:longint;end;

n,i,x,r,sum:longint;

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

use:array[1..200] of boolean;

function dfs(i:longint):longint;

var

p:longint;

begin

use[i]:=true;p:=f[i];

while p0 do

begin

if not use[zz[p].who] then dfs(zz[p].who);

p:=zz[p].link;

end;

end;

begin

readln(n);

for i:=1 to n do

begin

read(x);

while x0 do

begin

inc(r);

zz[r].link:=f[i];

zz[r].who:=x;

f[i]:=r;

read(x);

end;

end;

for i:=1 to n do if not use[i] then

begin

inc(sum);

dfs(i);

end;

writeln(sum);

end.

这道题 绝对有问题

经典floodfill

两次dfs

procedure dfs1(k:longint);

var

i:longint;

begin

used[k]:=true;

for i:=1 to n do

if (a[k,i])and(not used[i]) then dfs1(i);

inc(p);b[p]:=k;

end;

procedure dfs2(k:longint);

var

i:longint;

begin

used[k]:=true;

for i:=1 to n do

if (a)and(not used[i]) then dfs2(i);

end;

按题上的意思，每组内是可以互相交流的，但是如果用dfs，结果只对一个，晕！

要是这样的话：

6

2 0

3 0

4 0

5 0

6 0

dfs就只会说有1组，不可能！！！！！！

記錄号 Flag 得分 記錄信息 環境 評測機 程序提交時間

R1118279 Accepted 100 From zgx－

　 P1022 FPC Vivid Puppy 2009-1-19 22:44:23

From Vivian Snow

Victoria的舞會2 Victoria的舞會 系列

編譯通過...

├ 測試數據 01：答案正确... 0ms

├ 測試數據 02：答案正确... 0ms

├ 測試數據 03：答案正确... 0ms

├ 測試數據 04：答案正确... 0ms

├ 測試數據 05：答案正确... 0ms

├ 測試數據 06：答案正确... 0ms

├ 測試數據 07：答案正确... 0ms

├ 測試數據 08：答案正确... 0ms

├ 測試數據 09：答案正确... 0ms

├ 測試數據 10：答案正确... 0ms

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

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

简单图题，

但没学过图的先别做，

http://plfxy.blog.hexun.com/27241693_d.html

解题报告

编译通过...

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

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

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

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

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

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

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

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

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

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

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

program ex1;

var

i,j,n,total:integer;

a:array[1..200,1..200]of integer;

b:array[1..200]of integer;

d:array[1..200]of boolean;

procedure dfs(k:integer);

var

i,j:integer;

begin

for i:=1 to b[k] do begin

if d[a[k,i]] then begin

d[a[k,i]]:=false;

dfs(a[k,i]);

end;

end;

end;

begin

readln(n);

total:=0;

for i:=1 to n do begin

j:=1;

read(a);

while a0 do begin

inc(j);read(a);

end;

b[i]:=j-1;

readln;

end;

fillchar(d,sizeof(d),true);

for i:=1 to n do begin

if d[i] then begin

d[i]:=false;

dfs(i);

inc(total);

end;

end;

writeln(total);

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

var

a:array[1..200,1..200] of integer;

f:array[1..200] of boolean;

i,j,n,k:integer;

procedure dfs(l:integer);

var

i,j:integer;

begin

f[l]:=false;

for i:=1 to n do

if f[i] and (a[l,i]=1) then

dfs(i);

end;

begin

readln(n);

for i:=1 to n do

begin

read(k);

while k0 do

begin

a:=1;

read(k);

end;

end;

fillchar(f,sizeof(f),true);

k:=0;

for i:=1 to n do

if f[i] then

begin

dfs(i);

inc(k);

end;

writeln(k);

end.

一次AC!

就是图的遍历嘛！有那么麻烦吗？？？

program p1023;

var

a:array[1..200,1..200] of boolean;

b:array[1..200] of boolean;

ans,n,k,i:integer;

procedure doit(k:integer);

var

i:integer;

begin

for i:=1 to n do

if a[k,i] then if not(b[i]) then begin b[i]:=true;doit(i);end;

end;

begin

readln(n);

ans:=0;

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

fillchar(b,sizeof(b),0);

for i:=1 to n do

begin

k:=20000;

while not(k=0) do

begin

read(k);

if not(k=0) then a:=true;

end;

readln;

end;

for i:=1 to n do

begin

if not(b[i]) then

begin

inc(ans);

doit(i)

end;

end;

writeln(ans);

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

const maxn=200;

var

n,i,x,ans:integer;

b:array[1..maxn] of boolean;

t:array[1..maxn,1..maxn] of boolean;

procedure dfs(i:integer);

var j:integer;

begin

b[i]:=true;

for j:=1 to n do

if (not b[j]) and (t)

then dfs(j);

end;

begin

readln(n);

fillchar(b,sizeof(b),false);

fillchar(t,sizeof(t),false);

for i:=1 to n do

begin

read(x);

while x0 do

begin

t:=true;

read(x);

end;

end;

ans:=0;

for i:=1 to n do

begin

if b[i]=false

then inc(ans);

dfs(i);

end;

writeln(ans);

end.

虽然用floyd就对了

但对题意仍然不理解.....

没有编译，没测样例，直接AC

光打代码了

对于一个连通的有向图G，存在一个点v属于G的顶点集V，能够从这个出发，遍历V中其他的点。

故，纯并查集。