@sztom 2019-11-22T05:53:50.000000Z 字数 3748 阅读 104

浅析拓扑排序

图论九讲

1 拓扑排序的定义

对一个有向无环图(Directed Acyclic Graph简称DAG) $G$ 进行拓扑排序，是将 $G$ 中所有顶点排成一个线性序列，使得图中任意一对顶点 $u$ 和 $v$ ，若边 $u \rightarrow v \in E(G)$ ，则u在线性序列中出现在 $v$ 之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

其实，就是给一个有向无环图一个遍历的顺序。

但对于任意一条边 $u \rightarrow v$ 我们还要让 $u$ 排在 $v$ 前面，所以我们可以通过入度来计算。

2 拓扑排序解决的问题

拓扑排序解决类似于 $i$ 必须排在 $j$ 前的问题。
例如：
3必须排在5前；
4必须排在3前；
1必须排在2前；
5必须排在1前；
那么，顺序可能是4 3 5 1 2

3 拓扑排序的实现

后面拓扑要用入度，可以在建图时顺手加上。

for (int i = 1; i <= m; i++) {
    scanf ("%d%d", &a, &b);
    g[a].push_back(b);
    rd[b]++;
}

我们先把每个入度为零的点入队。
然后再取出队首，遍历所有它能到达的边，删除从它出发的边（到达的点入度-1）。
判断被遍历到的点中有没有入度为零的点。如果有，就把它入队。
如果队列为空，退出函数

代码实现：

void topu () {
    for (int i = 1; i <= n; i++) {
        if (rd[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.top();
        s.push(u);
        q.pop();
        for (unsigned i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            rd[v]--;
            if (rd[v] == 0) {
                q.push(v);
            }
        }
    }
}

4 拓扑排序的应用

拓扑排序一般用来给DAG一个遍历的顺序，有了顺序，我们就可以跑DP啦！

4.1 逃生（hdu4857)

这很明显是一道差分约束, 啊不，拓扑的题。

但是，我们还要把编号小的放在前面。

我们可以想到用优先队列解决这个问题。

代码与拓扑的模板很相似，代码就不放出来了。

4.2 缩点【模板】P3387

这道题看上去只要缩点后，再跑DP, 但问题是DP的顺序是什么：

我们可以想到用拓扑给缩完点后的图一个遍历的顺序。

缩点：

void Tarjan (int u) {
    deep++;
    dfn[u] = deep;
    low[u] = deep;
    s.push(u);
    ins[u] = 1;
    for (unsigned i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (!dfn[v]) {
            Tarjan (v);
            low[u] = min (low[u], low[v]);
        } else if (ins[v]) {
            low[u] = min (low[u], low[v]);
        }
    }
    if (low[u] == dfn[u]) {
        color[u] = u;
        dis[u] += val[u];//dis是记环的权值用的， val是每个点自己的权值
        while (s.top() != u) {
            color[s.top()] = u;//我们可以直接把环的编号记为缩点的编号
            dis[u] += val[s.top()];
            ins[s.top()] = 0;
            s.pop();
        }
        ins[u] = 0;
        s.pop();
    }
}

主函数内：

for (int i = 1; i <= n; i++) {
    if (!dfn[i]) {
        Tarjan(i);
    } 
}   
//缩点
for (int i = 1; i <= n; i++) {
    for (unsigned j = 0; j < g[i].size(); j++) {
        int v = g[i][j];
        if (color[i] != color[v]) {
            g1[color[i]].push_back(color[v]);//缩完点后重新建的图
            rd[color[v]]++;//入度
        }
    }
}

这道题的DP比较简洁，动态转移方程：（有点类似于松弛操作）， $f_v = \max \{f_v, f_u + D_v\}$ 。

所以我们可以直接在拓扑时跑DP，以减少代码复杂度。

vector <int> g1[N]; 
queue<int> q;
int rd[N];
int ans;
int f[N];//f[i] 表示终点为i的最长路
void topu () {
    //把入度为0的入队列
    for(int i = 1; i <= n; i++){
        //判断是不是缩点 入度为0
        if(!rd[i] && color[i] == i){
            q.push(i);
            f[i] = dis[i];//初始化,这里的dis就是上面公式里的D
        }
    }
    while(!q.empty()){
        int u = q.front(); q.pop();
        for (unsigned i = 0; i < g1[u].size(); i++){
            int v = g1[u][i];
            f[v] = max (f[v], f[u] + dis[v]);
            rd[v]--;
            if (rd[v] == 0) {
                q.push(v);
            } 
        }
    }
    for (int i = 1; i <= n; i++) {
        ans = max(f[i], ans);
    } 
}

4.3 Ponds（hdu5438）

这道题就难了很多，要先处理几个子问题。

怎样把把所有能去掉的池塘都去掉？
其实拓扑排序就可以解决这个问题，每次把度数减一，然后判断度数是否为零或一，
如果是，则入队。
怎样计算所有的连通组件（连通块）的点数？
可以用dfs或并查集（个人感觉dfs好写）解决。
把每个连通分量的点数记录下来，顺手记下它们的值的和。
如果只有一个点的连通组件，怎么处理？
依题意，就可以不用管这个点。（加个特判）

上代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 10005;
long long t, n, m, cnt, ans;
long long val[N], color[N], col[N], du[N], sum[N];//连通组件的值的和
vector <long long> g[N];
queue <long long> q;
bool vis[N], book[N];//判断这个点是否能用
void dfs (int u) {//dfs
    color[u] = cnt;
    vis[u] = 1;
    for (unsigned i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (vis[v] || book[v]) {
            continue;
        }
        dfs(v);
    }
}
void topu () {//拓扑 
    for (int i = 1; i <= n; i++) {
        if (du[i] == 0 || du[i] == 1) {
            vis[i] = 1;
            book[i] = 1;
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (unsigned i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (vis[v]) {
                continue;
            }
            du[v]--;
            if (du[v] == 1 || du[v] == 0) {
                book[v] = 1;
                vis[v] = 1;
                q.push(v);
            }
        }
    }
}
void clean () {//记得初始化 
    cnt = 0;
    ans = 0;
    memset (val, 0, sizeof(val));
    memset (color, 0, sizeof(color));
    memset (col, 0, sizeof(col));
    memset (sum, 0, sizeof(sum));
    memset (du, 0, sizeof(du));
    memset (vis, 0, sizeof(vis));
    memset (book, 0, sizeof(book));
    for (int i = 0; i <= n + 5; i++) {
        g[i].clear();
    }
    while (!q.empty()) {
        q.pop();
    }
}
int main() {
    scanf ("%d", &t);
    while (t--) {//毒瘤的多组数据(#→⌒→)
        scanf ("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf ("%d", &val[i]);  
        }
        int a, b;
        for (int i = 1; i <= m; i++) {
            scanf ("%d%d", &a, &b);
            g[a].push_back(b);
            g[b].push_back(a);
            du[a]++;
            du[b]++;
        }
        topu();
        memset (vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i++) {
            if (!color[i] && !book[i]) {//神似Tarjan
                cnt++;
                dfs(i);
            }
        }
        for (int i = 1; i <= n; i++) {
            col[color[i]]++;
            sum[color[i]] += val[i];
        }
        for (int i = 1; i <= cnt; i++) {
            if (col[i] % 2 == 1) {//判断是否是由奇数个点组成的
                ans += sum[i];
            }
        }
        printf ("%lld\n", ans);
        clean();
    }
    return 0;
}

5 总结

拓扑只能处理DAG, 把图变成一个线性序列，利用这一点，就能解决大多数的拓扑的题了。