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 0
 

Sample Output
1 2 3
 

Author
xudyh
 

Source
2014 Multi-University Training Contest 8

5行题干能读错两个地方，真是服了自己了==

题意：给定n个点两个有个有向边，要求拓扑排序，并且如果有a->b->c，可以直接a->c .

想到拓扑排序最最害怕的是成环，而仔细分析这个题的条件，既然两两点之间都有一条有向边，我们想这样的一种情况：a->b->c  如果是a->c，答案显而易见，如果是c->a，按着正常的拓扑排序肯定是不行的，但是本题可以提前两步连边。再说如果是v->a->b->u的话，假设u是入度最大的点，再假设v不能两步之内到达u，即v不可以连接u以及一步之内可以到达u的点，那么上述这些点就必须连到v，但是这么一来v的入度就比u的入度大1（因为加上u->v）与假设矛盾。从这个可以看出，入度最大的点一定是其他所有点两步之内可以到达的，那么入度最大的点就是最后的点，以此类推。

再说一下，拓扑排序好多都不是非得套模板的，主要还是理解删点的思路

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <queue>
#include<vector>
using namespace std;
const int maxn=509;
int indeg[maxn];
bool vis[maxn];
char tmp[550];
int num[maxn];
int main()
{
    //freopen("cin.txt","r",stdin);
    int n;
    while(~scanf("%d",&n)&&n)
    {
        memset(indeg,0,sizeof(indeg));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            scanf("%s",tmp);
            for(int j=0;j<n;j++)
            {
                if(tmp[j]=='1')
                {
                    indeg[j+1]++;
                }
            }
        }
       // for(int i=1;i<=n;i++)printf("%d ",indeg[i]);
        bool flag=1;
        int count=n,mx;
        while(flag)
        {
            flag=0,mx=-1;
            for(int i=1;i<=n;i++)
            {
                if(mx<indeg[i]&&vis[i]==0)
                {
                    flag=1;
                    mx=indeg[i];
                  //  printf("i=%d,mx=%d\n",i,mx);
                }
            }
            for(int i=1;i<=n;i++)
            {
                if(indeg[i]==mx&&vis[i]==0)
                {
                    vis[i]=1;
                    num[count--]=i;
                }
            }
        }
        for(int i=1;i<n;i++)printf("%d ",num[i]);
        printf("%d\n",num[n]);
    }
    return 0;
}