Face++面试中遇到的问题，手写一个拓扑排序函数，数据按照链式存储，即每个点链表存储出度的点。
当时想出了一种解决方法，不过看了其他解法，感觉自己的方法有点复杂，不过时间复杂度都是O(n^2)。

我当时的想法：正序没法找到拓扑的前后顺序，但是反过来就迎刃而解。从结束点（出度为0）开始，入队列。然后将入度当前点的点加入队列中。这样就找到了反序的拓扑序列，然后利用栈的特点反转就得到答案了。
当时面试官还和我谈论验证这个解法，但我觉得没啥问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
提示：跟一般的排序不一样，这个用于有向无环图

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，
使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。

拓扑排序对应施工的流程图具有特别重要的作用，它可以决定哪些子工程必须要先执行，哪些子工程要在某
些工程执行后才可以执行。
*/

queue<int>q;
//priority_queue<int,vector<int>,greater<int>>q;
//优先队列的话，会按照数值大小有顺序的输出
//此处为了理解，暂时就用简单队列
int topo()
{
    for(int i=1;i<=n;i++)
    {
        if(indegree[i]==0)
        {
            q.push(i);  // 起点
        }
    }

    int temp;
    while(!q.empty())
    {
        temp=q.front();// 如果是优先队列，这里可以是top()
        printf("%d->",temp);
        q.pop();
        for(int i=1;i<=n;i++)// 遍历从temp出发的每一条边，入度--
        {
            if(map[temp][i])
            {
                indegree[i]--;
                if(indegree[i]==0)q.push(i);
            }
        }
    }
}