Problem1872--寻找虫虫

1872: 寻找虫虫

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

小虫虫由于出来找食物飞走了,小红红回到学校之后发现虫虫不见了,好在他在虫虫的身上装了定位。小红红跟着定位来到了一个迷宫,这个迷宫很复杂,几乎每条道路都是交错的,为了能快的找到虫虫,你能帮助小红红判断该路径是否存在回路嘛?
Tips:
  在离散数学的定义下:在某个集合上的偏序得出全序的过程称为拓扑排序。
  偏序:若集合S上的关系R为自反,反对称和传递的,则称R是集合S上的偏序关系
  设R是集合S上的偏序,若对于每个x,y∈xRy或yRx,则称R为集合S的全序。
  拓扑排序的流程如下:
           1.  在有向图中选取一个没有前驱节点的点输出
           2.  从图中删除该顶点和所有以该点为尾的弧
一直重复以上步骤,直至顶点全部输出,或图中存在环为止。
拓扑排序结果可能不唯一,于是设置一规则:在入度为0存在多个结点时,按照结点序号从大到小处理。具体见样例。

Input

输入的第一行包含一个整数n,表示有n个节点。n不超过50
之后的n行中有整数0和1,对于第i行j列的值,若为1则表示i与j两点有边连接且又向的i点指向j点,若为0则没有边。保证不存在点的自回路(即i == j 时的值为0)

Output

若读入的有向图含有回路,输入"can not find the bug"
若没有回路,则按照题目的描述依次输出图的拓扑排序后的有序数列,每个整数后输出一个空格。
注意尾行的换行。

Sample Input Copy

4
0 1 0 0
0 0 1 0
0 0 0 0
0 0 1 0

Sample Output Copy

3 0 1 2 

Source/Category