hdoj1285 拓撲排序，hdoj1285拓撲
題目鏈接
分析：
很明顯，一看就是拓撲排序。 看似簡單， 暗藏武器啊。 第一次做的時候一邊拓撲排序一邊標記他們的深度， 例如題中給的例子 {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[505], e[505][505], ru[505];
void topu()
{
int sum = 0;
int flag = 1;
while(sum < n)
{
for(int i = 1; i <= n; i++)
{
if(v[i] == 0 && ru[i] == 0)
{
v[i] = 1;
if(flag == 1)
{printf("%d", i);flag = 0;}
else
printf(" %d", i);
for(int j = 1; j <= n; j++)
{
if(e[i][j] == 1)
{
ru[j]--;
e[i][j] = 0;
}
}
sum++;
break;
}
}
}
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
memset(e, 0, sizeof(e));
memset(v, 0, sizeof(v));
memset(ru, 0, sizeof(ru));
for(int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
if(e[x][y] == 0)
{
e[x][y] = 1;
ru[y]++;
}
}
topu();
cout << endl;
}
return 0;
}
View Code
