编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

连通分量=1时第二问=0

Kosaraju学起来好快~

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

这不是USACO的原题么。。直接强连通分量阿。。

求强连通的基础题

对于n

我用floyd过的

一遍

7楼：

反例：

12

34

R=C=0

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

囧 我交了三次

交的时候卡了一下 结果通过里面我就占了两个名字 o(╯□╰)o

hydralisk　fjxmlhx　Shouler_Akai　ghostmea　陈亮宇　陈亮宇　

强连通缩点为拓扑图后。

设入度为0点数为x

出度为0点数为y

下面第一问：

答案至少为x，答案为x时可行。

下面第二问：

若只有一个点，则答案为0；否则答案至少为max(x,y)，然后考虑构造方法：

对于多个连通快

设每个连通块入度为0的点只有1个

设每个连通块出度为0的点为k个

设k>1

则k-1个点连向自己连通快入度为0的点

剩下一个点连到其他连通块的入度为0的点

其他情况类似，不一一列举.所以当点>1时，答案为max(x,y)

easy..

一次AC。

我用了个很简单的方法

设入度为0的点有R个

出度为0的点有C个

A:max(R,1);

B:max(R,C);

可是第7个点错了

谁能说下错在哪里 小弟不胜ORZ

第二小问,要是有分成好几块的话该怎么处理啊?

要是一块就简单了...

只拿了82分丫丫

Orz 1s……

求强连通分量我还是喜欢写Tarjan算法，毕竟只要一次DFS……

先将强连通分量缩成点，然后再求入度和出度为0的强连通分量，第一问输出入度为0的强连通分量，第二问输出入度和出度为0较大的那个，ps。如果只有一个强连通分量则输出1 我很懒直接floyd的（Kosaraju算法比较优秀）

const maxn = 101;

var

a : array [0..maxn,0..maxn] of boolean;

lt : array [0..maxn] of longint;

v , ru , chu : array [0..maxn] of boolean;

n , tot , rud , chud : longint;

procedure init;

var i , x , tot : longint;

begin

readln(n); fillchar(a,sizeof(a),0); fillchar(v,sizeof(v),0); ru := v; chu := v;

for i := 1 to n do

begin

read(x); while x 0 do begin a := true; read(x); end;

readln;

end;

end;

procedure main;

var i , j , k : longint;

begin

for k := 1 to n do

for i := 1 to n do

for j := 1 to n do

a := a or (a and a[k,j]);

for i := 1 to n do

if not v[i] then

begin

inc(tot); lt[tot] := i; v[i] := true;

for j := 1 to n do if a and a[j,i] then v[j] := true;

end;

for i := 1 to tot do

for j := 1 to tot do

if i j then

begin

if a[lt[i],lt[j]] then chu[i] := true;

if a[lt[j],lt[i]] then ru [i] := true;

end;

rud := 0; chud := 0;

for i := 1 to tot do

begin

if not ru [i] then inc( rud);

if not chu[i] then inc(chud);

end;

writeln(rud);

if tot = 1 then begin writeln(0); exit; end;

if chud > rud then writeln(chud) else writeln(rud);

end;

begin

init;

main;

end.