# HDU - 4948 Kingdom 拓扑排序

## 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.

```3
011
001
000
0```

`1 2 3`

## 题解

```#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int mp[maxn][maxn];
int ans[maxn],d[maxn];
int n;
int cnt;
int main(){
while(true){
scanf("%d",&n);
if(n == 0)break;
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
mp[i][j] = 0;
for(int i = 1;i <= n;++i){
ans[i] = 0;
d[i] = 0;
}
cnt = n;
getchar();
for(int i = 1;i <= n;++i){
for(int j = 1;j <= n;++j){
char ch;
scanf("%c",&ch);
mp[i][j] = (int)(ch - '0');
if(mp[i][j])d[j]++;
}
getchar();
}
while(cnt != 0){
int mx = -1;
int pos = -1;
for(int i = 1;i <= n;++i){
if(mx < d[i]){
mx = d[i];
pos = i;
}
}
ans[cnt--] = pos;
d[pos] = -1;
}
for(int i = 1;i <= n;++i)
printf("%d ",ans[i]);
printf("\n");
}
return 0;
}﻿​```
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments Title - Artist
0:00