Description

有一張N個(gè)點(diǎn)，M1條有向邊，M2條無(wú)向邊組成的混合圖。詢問(wèn)一個(gè)給所有無(wú)向邊定向的方案。使得最終的圖中沒(méi)有環(huán)。保證一定有解。

Input

第一行，三個(gè)數(shù)字N,M1,M2。
接下來(lái)M1+M2行，每行兩數(shù)字Ai,Bi。表示一條邊。
前M1條是有向邊。方向是Ai到Bi。

Output

輸出M2行，按輸出順序輸出為無(wú)向邊確定的方向。Ai Bi或Bi Ai。
有多解時(shí)輸出任意解。

題解

對(duì)原圖做拓?fù)渑判?#xff0c;得到每個(gè)點(diǎn)的入隊(duì)時(shí)間，加邊的時(shí)候把邊定向?yàn)閺娜腙?duì)時(shí)間早的點(diǎn)到晚的點(diǎn)，原來(lái)的入隊(duì)順序就依然成立，就無(wú)環(huán)了。

代碼

typearr=recordy,next:longint;end; varn,nm,m1,m2:longint;e:array [0..400001] of arr;ls,f,q,b,h:array [0..200001] of longint;procedure add(x,y:longint); begininc(nm);e[nm].y:=y;e[nm].next:=ls[x];ls[x]:=nm; end;procedure topsort; varhe,ta,i,t,v:longint; beginhe:=1; ta:=0;for i:=1 to n doif f[i]=0 thenbegininc(ta);q[ta]:=i; b[i]:=1;end;while he<=ta dobegint:=q[he];i:=ls[t];while i<>0 dobeginv:=e[i].y;dec(f[v]);if f[v]=0 thenbegininc(ta);q[ta]:=v; b[v]:=1;end;i:=e[i].next;end;inc(he);end; end;procedure init; vari,u,v:longint; beginreadln(n,m1,m2);nm:=0;for i:=1 to m1 dobeginreadln(u,v);add(u,v);inc(f[v]);end;topsort;for i:=1 to n doh[q[i]]:=i;for i:=1 to m2 dobeginreadln(u,v);if h[u]<h[v] then writeln(u,' ',v)else writeln(v,' ',u);end;end;begininit; end.

轉(zhuǎn)載于:https://www.cnblogs.com/zyx-crying/p/9319587.html

總結(jié)

以上是生活随笔為你收集整理的混合图 (Standard IO)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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