[图论]拓扑排序

来源： http://www.cnblogs.com/skywang12345/p/3711489.html

拓扑排序

拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

这样说，可能理解起来比较抽象。下面通过简单的例子进行说明！
例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。

在拓扑排序中，如果存在一条从顶点A到顶点B的路径，那么在排序结果中B出现在A的后面。

步骤

1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological)；
2. 把所有没有依赖顶点的节点放入Q；
3. 当Q还有顶点的时候，执行下面步骤：
   1. 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中);对n每一个邻接点m(n是起点，m是终点);
   2. 去掉边$$$$;如果m没有依赖顶点，则把m放入Q;

注：顶点A没有依赖顶点，是指不存在以A为终点的边。

模板

struct Edge { int nxt, to, val; };
Edge e[maxn];
queue<int>q;
int cnt = 0, head[maxn];
void adde(int u, int v, int val)
{
    cnt++; e[i].to = v; e[i].nxt = head[u]; e[i].val = val; head[u] = cnt;
}

int main()
{
///////////////////////////////////////////////////////
    //在输入中计算终点的入度
    for (int i = 1; i <= n; i++)
    {
        cin >> x >> y >> val;
        adde(x, y, val);//(单向加边或双向加边)
        in[y]++;
    }
    //入队
    for (int i = 1; i <= n; i++)
        if (!in[i])    q.push(i);
    while (!q.empty())
    {
        int now = q.front(); q.pop();
        for (int i = head[now]; i; i = e[i].nxt)
        {
            in[e[i].to]--;
            if (!in[e[i].to])    q.push(e[i].to);
        }
    }
////////////////////////////////////////////////////////
}