2822 爱在心中

  时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

 

题目描述 

Description

“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又让我们此刻相逢Our Home。”

在爱的国度里有N个人，在他们的心中都有着一个爱的名单，上面记载着他所爱的人（不会出现自爱的情况）。爱是具有传递性的，即如果A爱B，B爱C，则A也爱C。

如果有这样一部分人，他们彼此都相爱，则他们就超越了一切的限制，用集体的爱化身成为一个爱心天使。

现在，我们想知道在这个爱的国度里会出现多少爱心天使。而且，如果某个爱心天使被其他所有人或爱心天使所爱则请输出这个爱心天使是由哪些人构成的，否则输出-1。

输入描述 

Input Description

第1行，两个数N、M，代表爱的国度里有N个人，爱的关系有M条。

第2到第M+1行，每行两个数A、B，代表A爱B。

输出描述 

Output Description

第1行，一个数，代表爱的国度里有多少爱心天使。

第2行，如果某个爱心天使被其他所有人和爱心天使所爱则请输出这个爱心天使是由哪些人构成的（从小到大排序），否则输出-1。

样例输入 

Sample Input

样例输入1：

6 7

1 2

2 3

3 2

4 2

4 5

5 6

6 4

样例输入2：

3 3

1 2

2 1

2 3

样例输出 

Sample Output

样例输出1：

2

2 3

样例输出2：

1

-1

数据范围及提示 

Data Size & Hint

各个测试点1s

分类标签 Tags 

 

题解：一道比较明显的tarjan强连通分量，和BZOj1051基本一样，值得注意几点——1.由于有可能存在整个图不连通的情况，同时更有可能从1#点出发不能到达很多点（比如1#的前驱们），所以不要直接来个tarjan(1)就想了事，建议直接每个点跑一下（很明显之前被跑过的点可以在本次无视之，而且实际上也就是经过了M条边而已，所以不必担心时间问题）  2.这题里面的“爱心天使”绝对不完全等价于全部强连通分量——注意分量只有一个点的情况，这时候可不算“爱心天使”  3.看样子codevs上面此题数据有些小（虽然没标明数据规模），我在bzoj上面148ms，在这上就9ms？！？！呵呵呵，而且我的程序后面很明显有比较冗余的语句，完全可以不必那么写的

That's all。。。别的没了。。。（只要会tarjan）

1 type  2         point=^node;  3         node=record  4                 g:longint;  5                 next:point;  6         end;  7 var  8         i,j,k,l,m,n,h,t,ans:longint;  9         a:array[-1..20000] of point; 10         ss,s:array[0..20000] of boolean; 11         low,dfn,f,b,c,d:array[0..20000] of longint; 12         p:point; 13 function max(x,y:longint):longint;inline; 14         begin 15                 if x>y then max:=x else max:=y; 16         end; 17 function min(x,y:longint):longint;inline; 18         begin 19                 if x
     
      nil do 35                         begin 36                                 if s[p^.g]=false then 37                                         begin 38                                                 tarjan(p^.g); 39                                                 low[x]:=min(low[x],low[p^.g]); 40                                         end 41                                 else if ss[p^.g] then low[x]:=min(low[x],dfn[p^.g]); 42                                 p:=p^.next; 43                         end; 44                 if low[x]=dfn[x] then 45                         begin 46                                 inc(ans); 47                                 while f[t+1]<>x do 48                                         begin 49                                                 ss[f[t]]:=false; 50                                                 b[f[t]]:=ans; 51                                                 dec(t); 52                                         end; 53                         end; 54         end; 55 begin 56         readln(n,m); 57         for i:=1 to n do a[i]:=nil; 58         for i:=1 to m do 59                 begin 60                         readln(j,k); 61                         add(j,k); 62                 end; 63         fillchar(s,sizeof(s),false); 64         fillchar(ss,sizeof(ss),false); 65         fillchar(f,sizeof(f),0); 66         fillchar(low,sizeof(low),0); 67         fillchar(dfn,sizeof(dfn),0); 68         fillchar(b,sizeof(b),0);ans:=0;h:=0;t:=0; 69         for i:=1 to n do if b[i]=0 then 70                 tarjan(i); 71         fillchar(c,sizeof(c),0);l:=ans; 72         for i:=1 to n do inc(c[b[i]]); 73         for i:=1 to ans do if c[i]=1 then dec(l); 74         writeln(l); 75         fillchar(d,sizeof(d),0); 76         for i:=1 to n do 77                 begin 78                         p:=a[i]; 79                         while p<>nil do 80                                 begin 81                                         if b[i]<>b[p^.g] then inc(d[b[i]]); 82                                         p:=p^.next; 83                                 end; 84                 end; 85         l:=-1; 86         for i:=1 to ans do 87                 begin 88                         if d[i]=0 then 89                                 begin 90                                         if l=-1 then 91                                                 l:=i 92                                         else 93                                                 begin 94                                                         writeln(-1); 95                                                         halt; 96                                                 end; 97                                 end; 98                 end; 99         if l=-1 then100                 begin101                         writeln(-1);102                         halt;103                 end;104         a[0]:=nil;k:=0;105         for i:=1 to n do106                 if b[i]=l then107                         begin108                                 add(0,i);109                                 inc(k);110                         end;111         if k<2 then112                 begin113                         writeln(-1);114                         halt;115                 end;116         p:=a[0];117         a[-1]:=nil;118         while p<>nil do119                 begin120                         add(-1,p^.g);121                         p:=p^.next;122                 end;123         p:=a[-1];124         while p<>nil do125                 begin126                         write(p^.g);127                         if p^.next<>nil then write(' ');128                         p:=p^.next;129                 end;130         writeln;131         writeln;132 end.