拓撲排序 --- hdu 4948 : KingdomKingdom

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 142    Accepted Submission(s): 84

Special Judge

Problem Description

Teacher Mai has a kingdom consisting of n cities. He has planned the transportation of the kingdom. Every pair of cities has exactly a one-way road.

He wants develop this kingdom from one city to one city.

Teacher Mai now is considering developing the city w. And he hopes that for every city u he has developed, there is a one-way road from u to w, or there are two one-way roads from u to v, and from v to w, where city v has been developed before.

He gives you the map of the kingdom. Hope you can give a proper order to develop this kingdom.

Input

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains an integer n (1<=n<=500).

The following are n lines, the i-th line contains a string consisting of n characters. If the j-th characters is 1, there is a one-way road from city i to city j.

Cities are labelled from 1.

Output

If there is no solution just output "-1". Otherwise output n integers representing the order to develop this kingdom.

Sample Input

3

011

001

000

Sample Output

1 2 3

Source

Mean: 

給你一個有n個城市(結點)有向圖，現在要發展這些城市，每兩個城市之間有且隻有一條單向邊。

發展城市必須要滿足一下條件：

當發展城市w的時候，其他已經發展的城市到w的距離必須小于等于2。

現在要你輸出發展的順序。

analyse:

題目說每兩個點之間至少有一條邊，是以說資料保證了給的圖一定是競賽圖。

由此可知，不能構造的情況是不存在的，也就是說可不能輸出-1。

我們隻需要對這個圖進行一個逆拓撲排序，然後輸出就可。

Time complexity：O(n^2)

Source code：

　　

沒想到這題資料這麼水，直接對入度從大到小排序，然後輸出就可：