7/29 拓扑排序

所谓”拓扑排序“，就是指将一个有向无环图G的所有顶点排成一个线性序列，使得有向无环图G的 边集中的任意一条边,始终满足u出现在v的前面。

所以实现拓扑排序其实非常简单，只需要找到入度为0的节点。然后删除与之相连的边，更新入度即可，直到所有点都被遍历过即可。

来道板子题

hdu 1285 

// Problem: 确定比赛名次
// Contest: HDOJ
// URL: http://acm.hdu.edu.cn/showproblem.php?pid=1285
// Memory Limit: 65 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include 

using namespace std;
const int N = 505;
int g[N][N];
int in[N], out[N];
void topsort(int n)
{
    int k = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (!in[j])
            {
                k = j;
                out[i] = j;
                in[j]--;
                break;
            }
        }
        for (int j = 1; j <= n; j++)
        {
            if (g[k][j] == 1)
            {
                g[k][j] = 0;
                in[j]--;
            }
        }
    }
}
int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        memset(g, 0, sizeof(g));
        memset(in, 0, sizeof(in));
        while (m--)
        {
            int x, y;
            cin >> x >> y;
            if (g[x][y])
                continue;
            g[x][y] = 1;
            in[y]++;
        }
        topsort(n);
        for (int i = 1; i <= n; i++)
        {
            if (i == n)
                printf("%dn", out[i]);
            else
                printf("%d ", out[i]);
        }
    }
}