题解 - Vijos

0

今夜请你停驻 LV 8 @ 2012-08-04 15:55:34

我还是不懂这和1022有什么关系……明显不一样的嘛能AC是数据的问题喂

——————————————————————————————————

输入格式就是前向星，所以直接用前向星表达图

然后Floodfill，但是不是求强连通分量

强连通分量是“任两个结点都可到达”

而这个没这么严格的……

枚举没有访问过的结点，然后BFS依次标记可以从“这个结点”到达的结点

统计一共枚举了多少个没有访问过的结点（不是BFS访问过是最外层循环枚举的结点）即可

——————————————————————————————————

注意事项：和1022对抄代码的时候别抄错了。。。

0

maxx LV 9 @ 2012-07-21 20:42:05

我去，这道题和1022有什么区别吗……

直接粘1022程序即可

0

beckydzau LV 8 @ 2012-07-21 10:07:03

虽然我也是直接copy1022的程序..但个人觉得应该是先用强连通找块再找入度为0的块吧..水过~~

0

dydcfg LV 7 @ 2010-07-07 18:58:36

mfset...............

program vj1023;

const

maxn=201;

var

mfset:array[-1..maxn] of longint;

n:longint;

function find(x:longint):longint;

var

i,j,k:longint;

begin

if mfset[x]=0 then exit(x);

j:=mfset[x];

while j0 do

begin

i:=j;

j:=mfset[i];

end;

k:=x;

while mfset[k]0 do

begin

j:=mfset[k];

mfset[k]:=i;

k:=j;

end;

exit(i);

end;

procedure datain;

var

i,j,x,y:longint;

begin

readln(n);

fillchar(mfset,sizeof(mfset),0);

for i:=1 to n do

begin

read(j);

x:=find(i);

while j0 do

begin

y:=find(j);

if xy then

mfset[y]:=x;

read(j);

end;

readln;

end;

end;

procedure main;

var

i,j:longint;

begin

j:=0;

for i:=1 to n do

if mfset[i]=0 then inc(j);

writeln(j);

end;

begin

datain;

main;

end.

0

donghexin LV 8 @ 2010-06-30 16:30:51

var

map:array[1..200,1..200]of longint;

link:array[1..200,0..200]of longint;

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

i,j,k,n,e,a,b,v,ans:longint;

procedure dfs(s:integer);

var

i,k,j:integer;

begin

visit:=true;

for i:=1 to link do

begin

if not(visit[link]) then map[v,link]:=1;

if not(visit[link]) then dfs(link);

end;

end;

procedure dfss(f:integer);

var

i,j,k:integer;

begin

for i:=1 to n do

if(not(visit[i]))and(map=1)and(map[f,i]=1) then

begin

visit[i]:=true;

dfss(i);

end;

end;

begin

readln(n);

for i:=1 to n do

begin

inc(b);

read(a);

while a0 do

begin

map:=1;

inc(link);

link[b,link]:=a;

read(a);

end;

end;

for i:=1 to n do

begin

v:=i;

dfs(i);

fillchar(visit,sizeof(visit),false);

end;

b:=0;

while b=0 do

begin

b:=1;

for i:=1 to n do

if not(visit[i]) then

begin

inc(ans);

visit[i]:=true;

dfss(i);

end;

for i:=1 to n do

if not(visit[i]) then b:=0;

end;

write(ans);

end.

0

hannett1 LV 7 @ 2010-03-28 16:44:36

译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

#include

#include

#include

#include

using namespace std;

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

int ans=0,n;

int map[300][300],ind[300];

bool went[300];

int main() {

MS(map);

MS(ind);

MS(went);

void fil(int);

cin >>n;

int a;

for(int i=1;i>a;

map[i][a]=1;

ind[a]++;

} while(a!=0);

for(int i=1;i

0

Devil_MT LV 7 @ 2010-03-15 21:18:36

用强连通明显是错误的算法。

这数据太2了

应该是最小点基

sxb_201 @ 2015-08-25 18:33:57

为什么？？强连通不行？？？？！！！

0

E_珑FAV LV 8 @ 2009-11-10 11:21:50

汗了…………

同1022

囧了

无语

顺便纪念100题

0

Camel King LV 8 @ 2009-11-07 21:38:08

额...汗...和1022一样的题目，只是问题描述不一样罢了

求强连通分量个数

0

First_blood LV 9 @ 2009-11-05 22:11:07

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一个我认为是错的程序出的结果。。。。。

- -|||

0

lishunzhi LV 9 @ 2009-11-04 23:07:39

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var x,i,n,k,j,b1,ans:longint;

b:array[0..203,0..203]of boolean;

used:array[0..204]of boolean;

procedure dfs(v:longint);

var i:longint;

begin

for i:=1 to n do

if not(used[i])and(b[v,i])and(b) then

begin

used[i]:=true;

dfs(i);

end;

end;

begin

readln(n);

for i:=1 to n do

begin

read(x);

while x0 do

begin

b:=true;

read(x);

end;

readln;

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (b)and(b[k,j]) then b:=true;

fillchar(used,sizeof(used),false);

b1:=0;

ans:=0;

while b1=0 do

begin

b1:=1;

for i:=1 to n do

if not(used[i]) then

begin

used[i]:=true;

inc(ans);

dfs(i);

end;

for i:=1 to n do if not(used[i]) then b1:=0;

end;

writeln(ans);

end.

这也是我的P1022.....

0

jessie LV 7 @ 2009-11-03 11:16:06

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

jiayu888 LV 8 @ 2009-11-01 21:18:04

就是并查集入门的练习……

var

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

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

function getfather(x:integer):integer;

begin

if father[x]=0 then exit(x)

else

begin

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

exit(father[x]);

end;

end;

begin

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

readln(n);

for i:=1 to n do

begin

read(j);

while j0 do

begin

x:=getfather(i);

y:=getfather(j);

if xy then father[x]:=y;

read(j);

end;

readln;

end;

for i:=1 to n do

if father[i]=0 then inc(m);

writeln(m);

end.

0

胡征宇 LV 5 @ 2009-10-30 12:32:23

const maxn=200;

type re=record o,l:integer; q:array[1..maxn]of integer; end;

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

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

　　c:array[1..maxn]of re;

　　cc:re;

　　n,i,j,x,w,o:integer;

procedure bfs(x:integer);

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

　　q:array[1..maxn]of integer;

　　i,f,r,o:integer;

begin

f:=0; r:=1; q[1]:=x;

for i:=1 to n do b[i]:=true;

b[x]:=false;

while f

0

darin LV 10 @ 2009-10-23 17:00:32

dfs2次 = ac。。。。囧。。这是难度3么。。难怪通过率这么高。。。

0

song19931218 LV 9 @ 2009-10-07 13:22:20

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

最朴素的dfs，秒杀

0

lct_3 LV 7 @ 2009-10-06 22:13:44

有向图的最小点基..

0

violethill LV 10 @ 2009-10-05 18:34:03

floyd+贪心=ac

0

天涯残影 LV 8 @ 2009-10-05 15:59:18

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

strini LV 8 @ 2009-09-25 14:00:25

Toposort + floodfill, The data is so weak that I didn't need to consider the situation of cirles.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

题解

179 条题解

Victoria的舞会3

信息

状态

开发

支持

题解

179 条题解

Victoria的舞会3

信息

状态

开发

支持

还没有账户？

登录