2822 愛在心中

??時間限制: 1 s

?空間限制: 128000 KB ?題目等級 : 鉆石 Diamond? 題目描述?Description

“每個人都擁有一個夢，即使彼此不相同，能夠與你分享，無論失敗成功都會感動。愛因為在心中，平凡而不平庸，世界就像迷宮，卻又讓我們此刻相逢Our Home。”

在愛的國度里有N個人，在他們的心中都有著一個愛的名單，上面記載著他所愛的人（不會出現(xiàn)自愛的情況）。愛是具有傳遞性的，即如果A愛B，B愛C，則A也愛C。
如果有這樣一部分人，他們彼此都相愛，則他們就超越了一切的限制，用集體的愛化身成為一個愛心天使。
現(xiàn)在，我們想知道在這個愛的國度里會出現(xiàn)多少愛心天使。而且，如果某個愛心天使被其他所有人或愛心天使所愛則請輸出這個愛心天使是由哪些人構(gòu)成的，否則輸出-1。

輸入描述?Input Description

第1行，兩個數(shù)N、M，代表愛的國度里有N個人，愛的關(guān)系有M條。
第2到第M+1行，每行兩個數(shù)A、B，代表A愛B。

輸出描述?Output Description

第1行，一個數(shù)，代表愛的國度里有多少愛心天使。
第2行，如果某個愛心天使被其他所有人和愛心天使所愛則請輸出這個愛心天使是由哪些人構(gòu)成的（從小到大排序），否則輸出-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

數(shù)據(jù)范圍及提示?Data Size & Hint

各個測試點1s

分類標(biāo)簽?Tags?點此展開?

題解：一道比較明顯的tarjan強連通分量，和BZOj1051基本一樣，值得注意幾點——1.由于有可能存在整個圖不連通的情況，同時更有可能從1#點出發(fā)不能到達很多點（比如1#的前驅(qū)們），所以不要直接來個tarjan(1)就想了事，建議直接每個點跑一下（很明顯之前被跑過的點可以在本次無視之，而且實際上也就是經(jīng)過了M條邊而已，所以不必?fù)?dān)心時間問題） ?2.這題里面的“愛心天使”絕對不完全等價于全部強連通分量——注意分量只有一個點的情況，這時候可不算“愛心天使” ?3.看樣子codevs上面此題數(shù)據(jù)有些小（雖然沒標(biāo)明數(shù)據(jù)規(guī)模），我在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.

?

轉(zhuǎn)載于:https://www.cnblogs.com/HansBug/p/4276065.html

總結(jié)

以上是生活随笔為你收集整理的Codevs2822 爱在心中的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。