program p1626;

type shu=array[1..1001]of integer;

var n,m,i,j,x,y,k,s,ps:integer;

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

p,pp,ppp:shu;

d:boolean;

procedure sou(x,i:integer; g:shu);

var j,k:integer;

begin

g[x]:=i;

for j:=1 to n do

if a[x,j] then

begin

if j=i then

begin

for k:=1 to n do p[k]:=g[k];exit;

end;

if g[j]i then sou(j,i,g);

end;

end;

begin

readln(n,m);

for i:=1 to m do

begin

readln(x,y); a[x,y]:=true;

end;

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

for i:=1 to n do

sou(i,i,p);

i:=1;

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 inc(pp[p[i]]);

for i:=1 to n do if pp[i]>1 then inc(s);

writeln(s);

for i:=1 to n do

if pp[i]>1 then

begin

d:=true;

for j:=1 to n do

if ij then

if a[j,i] then d:=true

else d:=false;

if d then

begin

for j:=1 to n do

if p[j]=i then begin inc(ps); ppp[ps]:=j end;

for j:=1 to ps do

if j=1 then write(ppp[j]) else write(' ',ppp[j]);

writeln; halt;

end;

end;

writeln('-1');

end.

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

Unaccepted 有效得分：50 有效耗时：0ms

哪位大侠帮帮忙看一下哪里错了

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

好题 啊 强连通啊 我没学过

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

诧异了，我还不懂什么是缩点.....居然就白痴两次dfs一次过了.....

话说这个开头不是《爱因为在心中》吗，好怀念啊，这是我们初中大合唱的歌曲啊T^T

郁闷。。。。。。。。。。

c1忘写了。。。。。。。。。

90分 n次。。。。。。。。。

貌似又些麻烦了……

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

。。。我的AC率啊 &=.=&

第一遍（比赛的时候）

70.

1点错

2点超时

Floyd做的

现在

第二遍

Dfs.90.一点错。

第三遍

Dfs.80.2点错。格式错误/运行超时。

第四遍

以为是评测机的错误。。再提交一遍。。老样子。。

第五遍

AC..

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：90 有效耗时：0ms

那位神牛知道为什么

好多细节...

我看来还是很沙茶的说...

：

如果某个爱心天使被其他所有人【或！！】爱心天使所爱则请输出这个爱心天使是由哪些人构成的

飘过～～～

并查集A的，效率略微慢了点...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

爱心天使被其他所有人“和”爱心天使所爱

爱心天使被其他所有人“或”爱心天使所爱

到底是和还是或

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一次写Kosaraju，写的太墨迹了，还好秒杀了

先缩强连通，然后对于点数量>=2的染白色否则染黑色。然后对于每个白色检查是否有白色指向这个点或者所有点是否都对其有边。

http://cgang.ihost.tw/archives/95

没什么好说的。第一问求强连通分支，Kosaraju算法和tarjan算法皆可。第二问缩点，然后用floyd也行，dfs也行，按照题目描述判断就行。我判断的地方貌似有一点是n^3的，竟然也秒杀。数据弱……

做这题真是太郁闷了。

学习着写了tarjan算法，结果出现了这种情况

第一次：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Unaccepted 有效得分：90 有效耗时：0ms

第二次：

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

搞什么，大数据秒杀，巨小的数据超时。完全一样的程序，同一个评测器，30s后重交，AC……

欺负我第一次写tarjan？

编译通过...

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

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

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

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

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

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

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

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

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

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

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

Accepted 有效得分：100 有效耗时：361m

floyd居然能过……就是慢了点………………还不如写个dfs呢……

正向DFS+反向DFS=求强连通分量

每个强连通分量反向DFS时若能到达所有节点就是被所有人爱。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

dfs版也没秒杀。。为啥？是不是邻接矩阵慢？

ＯＯ═══∩═══ＯＯ

　　　　╭╬╮　　　　　　 　 ◢

-▁╭▅▇□□█▇▆▅▄▃▂▁(╳)█╮

　 ╰═▃_专机来顶▁∠════▔▔▔　

　 ╙O ╙O！↓

边可以这样改

for i:=1 to m do

with edge[i] do

begin

v1:=father[v1];

v2:=father[v2];

end;

之后再将所有不重复边抽取到另一个edge数组

另外，测评时莫名其妙地超时，交多次就0ms了.......

dfs+反方向边bfs

找环（强连通分量）

缩成一点

floyed

求第二问

1次ac!!!!!!!!!!!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

tmd，交了有10遍……

先求强连通分量，再找度为0的强连通分量，如果只有一个且包含点数大于1，那么把所有边取反，从这个分量中的点BFS，如果能到所有点，就符合要求

囧 一直以为只有两个人才能变成一个天使..