題目大意：好像就是先告訴你他要用26個(gè)字母的前n個(gè)字母，然后給你m條對(duì)這n個(gè)字母的限制，每一條限制這n個(gè)字母其中的兩個(gè)的先后關(guān)系，問你通過這些限制條件能不能確定這n的字母的序列。注意：當(dāng)存在沖突或者拓?fù)渑判虺晒r(shí)，之后的輸入不對(duì)結(jié)果造成影響。（一開始因?yàn)檫@個(gè)一直在wa）

思路：A<B即可以理解成存在邊A-B。n個(gè)點(diǎn)組成的圖，給你m條邊。問你該圖是否為DAG（無有向環(huán)圖）然后是否拓?fù)湫蛭ㄒ唬詈笄笸負(fù)湫颉ｊP(guān)于Kahn算法：找出所有入度為0的點(diǎn)，這些點(diǎn)都存入結(jié)果數(shù)組中（這些點(diǎn)拍成任意順序都可以，因?yàn)椴粫?huì)有其他點(diǎn)必須在它左邊）然后枚舉這些點(diǎn)（任意順序），依次判斷這個(gè)點(diǎn)的所有出邊（判斷之前在圖中刪除該邊），如果出邊的另一端的點(diǎn)，當(dāng)前入度（刪除邊之后）為0，就可以把他放入結(jié)果數(shù)組之中（他已經(jīng)保證了在以它為終點(diǎn)的所有的起點(diǎn)的右邊，以后再往數(shù)組里放的點(diǎn)，都能在它右邊），如果不是，就不入數(shù)組，但是刪的邊也不要還原（因?yàn)楝F(xiàn)在也已經(jīng)保證了，該邊的起點(diǎn)在終點(diǎn)左邊）。 網(wǎng)上查到了對(duì)這個(gè)算法更簡(jiǎn)單的描述：取出圖中所有入度為0的點(diǎn)，然后刪除這些點(diǎn)（包括其出邊），再一次取出所有入度為0的點(diǎn)。知道所有點(diǎn)都被取出。 

對(duì)于這道題所要求的拓?fù)渑判蛭ㄒ唬贙ahn算法實(shí)現(xiàn)過程中，不能有這么隨意，也就是說，一開始，入度為0的點(diǎn)只能有一個(gè)，然后每次對(duì)結(jié)果數(shù)組中的點(diǎn)，判斷其所有出邊的另一端是否可以進(jìn)入數(shù)組的時(shí)候，有且只有一個(gè)點(diǎn)可以進(jìn)去。然后下一次判斷出邊的點(diǎn)，也是唯一確定的了。如果某一次，進(jìn)入的點(diǎn)不止一個(gè)或者沒有點(diǎn)入隊(duì)，那么，不能確定該拓?fù)湫颍ㄔ谂袛嗤暝搱D為DAG的前提下）。 在網(wǎng)上查得另一種保證拓?fù)渑判蛭ㄒ坏姆椒ǎ瑢?duì)排序完成的數(shù)組中，每?jī)蓚€(gè)相鄰的點(diǎn)進(jìn)行一次判斷，判斷其之間是否有從左頂點(diǎn)指向右頂點(diǎn)的有向邊，如果沒有，那么我把這兩個(gè)點(diǎn)調(diào)換位置，一定可以得到另一個(gè)不同的拓?fù)湫蛄小?nbsp;

然而還有一個(gè)問題就是：必須寫出，一條一條讀入之后，讀入了第幾條邊的時(shí)候，該拓?fù)湫虼_定。 我可以加一條邊判斷一次嗎，雖然感覺很麻煩，但是它就是很麻煩啊^_^#，而且low，而且low，而且low。他并沒有給出m的大小，其實(shí)仔細(xì)想一下復(fù)雜度，如果給的這m條都是不重復(fù)的，那最多也就是26*25條，Kahn的話，復(fù)雜度我感覺應(yīng)該就是26個(gè)點(diǎn)，每個(gè)點(diǎn)25條出邊，也是25*26。乘在一起，一個(gè)測(cè)試實(shí)例復(fù)雜度大概就是422500，乍一看也不高啊。另一個(gè)問題是怎么判斷該無權(quán)有向圖，不存在有向環(huán)。即為DAG圖。注意也許該圖根本不連通。

注：不能用Bellman-Ford判斷一個(gè)圖是否存在正權(quán)環(huán)回路。

整整做了一整天，還是沒做出來。把所有后臺(tái)測(cè)試數(shù)據(jù)都找出來，就是有一組不對(duì)。明天改。還是代碼實(shí)現(xiàn)的問題，dfs、bfs要重新練。