拓扑排序

前言

在ICPC赛前的分工中我应该是要做数据结构、图论和字符串来着。前一阵学了KMP，打算最近再看看图论，从拓扑排序开始。

---

拓扑排序

拓扑排序并不是和冒泡、插排类似的排序算法，它用于在有向无环图（DAG）中对图的结点进行排序。

实现方法

Kahn算法：（其实是一种bfs）每次选择一个入度为零的点从图中删除（连带与他相连的边），更新临近点的入度，维护入度为零的点的集合（使用队列维护，对于题目特殊要求可以选用大根堆、小根堆），反复执行这个过程直到队列为空。若删除点数量为n，则确认图是DAG，以及求出节点序列。

DFS算法：递归访问节点并在回溯时记录节点顺序来实现拓扑排序。

我去查阅了一些题解和资料，发现很少有人去评论两种算法的高效性，不过我个人认为Kahn更好写，更易读，因此刷题时全部使用了Kahn算法。

代码

void topsort() {
    L.clear();
    priority_queue<int, vector<int>, greater<int> > q;	
    // 小根堆维护入度为零的点的集合，保证排序后字典序最小
    for(int i = 1; i <= n; ++i) 
        if(in[i] == 0) q.push(i);

    while(q.size()) {
        int u = q.top();
        q.pop();
        L.push_back(u);
        for(auto &i : G[u]) {
            if(--in[i] == 0) {
                q.push(i);
            }
        }
    }
}

一些要注意的点

很多题目不是Special Judge，也就是说对输出序列除了元素前后关系的要求，可能有一些其他要求，比如字典序最小，这种时候可以使用小根堆代替普通队列。但是有些时候输出顺序没有那么简单，如HDU4857逃生，为了使数字小的号码尽可能在前，需要使用反向拓扑+大根堆

void topsort() {
    priority_queue<int> s;
    for(int i = 1; i <= n; ++i) if(in[i] == 0) s.push(i);

    int cnt = n;
    while(!s.empty()) {
        int u = s.top(); s.pop();
        L[cnt--] = u;
        for(int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if(--in[v] == 0) s.push(v);
        }
    }
}

void solve() {
    for(int i = 1; i <= n; ++i) G[i].clear();
    memset(in, 0, sizeof(in));
    cin >> n >> m;

    for(int i = 1, x, y; i <= m; ++i) {
        cin >> x >> y;
        ++in[x];
        G[y].push_back(x);
    }

    topsort();
    for(int i = 1; i <= n; ++i) cout << L[i] << ' ';
    cout << '\n';
}

总结

之前遇到好多题题解有拓扑排序+一堆其他图论算法，包括求强连通分量、缩点等，并不像我最近刷的模板题那么简单。所以我打算下一步去复习Tarjin算法，以防真遇到题发现自己只会一半（笑）。