題目描述:
超哥來(lái)到一間密室，忽然一陣陰風(fēng)把門(mén)關(guān)上了。魔法學(xué)校的門(mén)需要魔力才能打開(kāi)，而超哥沒(méi)有那間密室的魔力。超哥繼續(xù)往密室深處走，發(fā)現(xiàn)一堆魔法瓶和一些古老的文字。上面寫(xiě)著：欲開(kāi)啟密室，需收集所有瓶中魔力。開(kāi)啟魔法瓶需嚴(yán)格按照順序，否則將焚毀密室…文字記載了一個(gè)N×N的0,1矩陣GN×N，還記錄了任意兩個(gè)魔法瓶之間的開(kāi)啟規(guī)則：你可以從任意一個(gè)魔法瓶開(kāi)始。魔法瓶j能在緊隨魔法瓶i之后被安全打開(kāi)，當(dāng)且僅當(dāng)Gi,j=1。魔法瓶j緊隨魔法瓶i之后被打開(kāi)，密室會(huì)被焚毀，當(dāng)且僅當(dāng)Gi,j=0。文字最后寫(xiě)道，任意兩個(gè)魔法瓶，都可以相鄰。即:Gi,j⊕Gj,i=1(?i≠j)你能幫超哥找到一個(gè)開(kāi)啟所有魔法瓶方案嗎？
輸入:
第一行一個(gè)整數(shù)N，魔法瓶的個(gè)數(shù)，接著N行，每行N個(gè)數(shù)，0或1。第i行第j列為1，表示開(kāi)啟第i個(gè)魔法瓶后，下一個(gè)開(kāi)啟的魔法瓶可以是j。保證矩陣 第i行第j列與 第j行第i列數(shù)值不同，第i行i列為0。N≤1000
輸出:
N個(gè)數(shù)，空格隔開(kāi)，表示打開(kāi)魔法瓶編號(hào)順序。
樣例輸入:
2
0 0
1 0
樣例輸出:
2 1
問(wèn)題分析：
該題的本質(zhì)即：
在一“特殊”有向圖中尋找一條不重復(fù)經(jīng)過(guò)某個(gè)點(diǎn)的可行路徑遍歷圖中所有點(diǎn)。
而這個(gè)圖究竟有多特殊呢？
該圖的特殊性描述如下：
1、該圖中任意兩點(diǎn)之間存在一條路徑；
2、該路徑為單向不可逆，即若存在A->B,則不存在B->A,反之亦然
由以上兩條特殊性可推出如下結(jié)論：
若存在一條路徑經(jīng)過(guò)圖中若干個(gè)點(diǎn)，例：2->1->3->4
則必存在圖中任意不在該路徑中的點(diǎn)可插入該路徑中使路徑連通：
假設(shè)該數(shù)組為arr，圖中任意不在該路徑中的點(diǎn)為5，則遍歷arr[5][2],arr[5][1],
arr[5][3],arr[5][4],若存在arr[5][num] = 1;則插入該數(shù)前，若不存在為1的值則插入路徑尾部，因?yàn)槿鬭rr[5][4] = 0;由特殊性2可知arr[4][5] = 1;即點(diǎn)4可到達(dá)點(diǎn)5。
java實(shí)現(xiàn)如下：
