时间限制: 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
题解:一道比较明显的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<y then min:=x else min:=y;
20 end;
21 procedure add(x,y:longint);inline;
22 var p:point;
23 begin
24 new(p);p^.g:=y;
25 p^.next:=a[x];a[x]:=p;
26 end;
27 procedure tarjan(x:longint);
28 var
29 p:point;
30 begin
31 inc(h);low[x]:=h;dfn[x]:=h;
32 inc(t);f[t]:=x;ss[x]:=true;s[x]:=true;
33 p:=a[x];
34 while p<>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 then
100 begin
101 writeln(-1);
102 halt;
103 end;
104 a[0]:=nil;k:=0;
105 for i:=1 to n do
106 if b[i]=l then
107 begin
108 add(0,i);
109 inc(k);
110 end;
111 if k<2 then
112 begin
113 writeln(-1);
114 halt;
115 end;
116 p:=a[0];
117 a[-1]:=nil;
118 while p<>nil do
119 begin
120 add(-1,p^.g);
121 p:=p^.next;
122 end;
123 p:=a[-1];
124 while p<>nil do
125 begin
126 write(p^.g);
127 if p^.next<>nil then write(' ');
128 p:=p^.next;
129 end;
130 writeln;
131 writeln;
132 end.