hdoj1285 拓扑排序

时间:2022-04-22 16:10:40

题目链接

分析: 
很明显,一看就是拓扑排序。 看似简单, 暗藏武器啊。 第一次做的时候一边拓扑排序一边标记他们的深度, 例如题中给的例子 {1 2;2 3;4 3 }。1的深度为1。 2、4的深度为2; 3的深度为3。 然后按深度的逆序输出深度相同的先输出小的。 其实不然啊!! 举个例子6个点, 边为{5, 3; 5,1; 5,4; 5,2; 3,1; 3,2; 6,4; 6,2; 4,2} 最好自己画一下, 看的更明白些!! 按我第一次思路 从1到6他们深度依次为1,1,2,2,3,3; 结果为5, 6,3, 4, 1, 2。 其实哩。正确结果应该为5, 3, 1, 6, 2, 4。 
最初没有比5、6大的数, 5〈 6,所以输出5。 这时相当于没有5了, 去掉5之后发现, 也没有比3大的数了, 3又小于6, 所以先输出3。 取掉3, 这时也没有比1大的数了, 在输出1………….直到输出所有点。

正确解题思路为: 
1)选一个入度为0的点p输出; 
2)从图中删除p点 
3)将p全部后继点的入度-1 
4)重复1-3,直到全部点都输出

#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std; int n, m, mx, v[], e[][], ru[];
void topu()
{
int sum = ;
int flag = ;
while(sum < n)
{
for(int i = ; i <= n; i++)
{
if(v[i] == && ru[i] == )
{
v[i] = ;
if(flag == )
{printf("%d", i);flag = ;}
else
printf(" %d", i);
for(int j = ; j <= n; j++)
{
if(e[i][j] == )
{
ru[j]--;
e[i][j] = ;
}
}
sum++;
break;
}
}
}
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
memset(e, , sizeof(e));
memset(v, , sizeof(v));
memset(ru, , sizeof(ru));
for(int i = ; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
if(e[x][y] == )
{
e[x][y] = ;
ru[y]++;
}
}
topu();
cout << endl;
}
return ;
}