模板 图论

本文记录一些基本的图论算法。

强连通分量分解

强连通分量分解常常用于缩点和求解2-SAT问题。

Tarjan算法

求一个图的强连通分量比较常用的一个方法是 Tarjan 算法。

Tarjan 算法基于深度优先搜索，每一个搜索到的强连通分量都是搜索树的一棵子树。同时也用到了栈。

Tarjan 算法用到了两个十分重要的数组：$dfn$ 和 $low$。两个数组均和节点相关。前者保存搜索时每个节点的时间戳（即被搜索到的次序），每个节点的时间戳各不相同，并且一旦确定就不再改变。后者保存每个节点本身及其子树，这些节点所能回溯到的在栈中的节点的 $dfn$ 的最小值。当最终得到 $dfn[v]$ 和 $low[v]$ 相等时，就说明 $v$ 及其子树构成一个强连通分量。

执行这个算法时分以下几个步骤：

1. 由于图不一定联通，对每一个点都应当遍历。如果 $dfn=0$ 就进入搜索。
2. 设当前节点为 $v$。把点加入栈中，更新 $dfn[v]$，并令 $low[v]=dfn[v]$。
3. 检查每一个 $v$ 可以到达的点，设为 $u$。若 $u$ 未被搜索过，就令其进入搜索，并更新 $low[v]=\min\lbrace low[v], low[u] \rbrace$。若 $u$ 已被搜索过且在栈中，就更新 $low[v]=\min\lbrace low[v], dfn[u] \rbrace$。（可以看出，两次更新均符合 $low$ 的定义）
4. 如果 $dfn[v]=low[v]$，就将 $v$ 及其子树所含节点从栈中弹出，弹出的这些节点构成一个强连通分量。对 $v$ 的搜索结束。

int dfn[100005], low[100005], D, in[100005]; 
int stack[100005], top;
void tarjan_scc(int id){
    dfn[id] = low[id] = ++D;
    in[id] = true;
    stack[top++] = id;
    int i = at[id], vv;
    while(i){
        vv = e[i].v;
        if(!dfn[vv]) tarjan_scc(vv), low[id] = min(low[id], low[vv]);
        else if(in[vv]) low[id] = min(low[id], dfn[vv]);
        i = e[i].nxt;
    }
    if(dfn[id] == low[id]){
        //do something
        do{
            top--;
            in[stack[top]] = false;
        }while(stack[top] != id);
    }
}

按照上面的算法过程得到的强连通分量的顺序是逆拓扑序。

Kosaraju算法

另一个常用的强连通分解算法为Kosaraju算法。

该算法基于以下两个事实：

1. 一个DAG的拓扑序即为该DAG在DFS之后的顶点的逆后序排列。
2. 有向图的两个顶点可以互相访问，那么这两个顶点在同一个强连通分量之中。

该算法的运行也很简单，只分三步：

1. 对当前图$G$进行DFS，得到所有点的后序遍历。
2. 对当前图$G$构造反图$G^-$。
3. 按照后序遍历编号从大到小对顶点进行检查，如果顶点未被DFS过就以该点为起点在$G^-$上进入搜索，每次搜索经过的所有点就构成一个强连通分量。

/* 在e_和at_保存了反图 */
int at_[10005] = {0}, cnt_ = 0, rk_cmp[10005], R = 0;
bool in[10005] = {0}; 
int st[10005], top = 0;
void dfs(int id){
    in[id] = true;
    for(int i = at[id]; i; i = e[i].nxt)
        if(!in[e[i].v]) dfs(e[i].v);
    st[top++] = id;
}
void rdfs(int id){
    in[id] = false;
    rk_cmp[id] = R;
    for(int i = at_[id]; i; i = e_[i].nxt)
        if(in[e_[i].v]) rdfs(e_[i].v);
}
void kosaraju(){
    for(int i = 1; i <= V; ++i)
        if(!in[i]) dfs(i);
    for(int i = top - 1; i >= 0; --i)
        if(in[st[i]]) R++, rdfs(st[i]);
}

该算法相较Tarjan算法比较麻烦，但能方便的得到强连通分量之间的拓扑序，因此可以较为方便地用于求解2-SAT问题。

2-SAT问题

给定一个布尔方程， 判断是否存在一组布尔变量的真值指派使整个方程为真的问题，被称为布尔方程的可满足性问题（SAT）。可以把布尔方程写成析取式的合取，即合取范式的形式。如果该布尔方程中，每个析取式至多只包含两个变量，就称该问题为2-SAT问题。

利用强连通分量分解可以在线性时间复杂度内解决2-SAT问题。把$a\vee b$改写成$(\neg a \rightarrow b) \wedge (\neg b \rightarrow a)$的形式，并且把每个变量拆成$a$和$\neg a$两个点，根据蕴含关系建立边。随后，对整个图进行强连通分量分解，易知在同一个强连通分量中的变量真值必须相同。

分解完成后，如果一个变量$a$和$\neg a$在同一个强连通分量中，那么显然这时无解。否则，可以根据强连通分量的拓扑序来给变量赋值，如果$a$所在分量的拓扑序在$\neg a$之后就令$a$为真，否则为假。这是为了保证$a\vee a$这样的条件可以得到满足。如此就完成了2-SAT问题的求解。

2-SAT问题可以推广，只要能将命题的形式写成合取范式，然后变形即可。

二分图

判定二分图

通常使用“一个图是二分图当且仅当这个图中没有奇环”的衍生结论：一个图是二分图当且仅当可以只用两种颜色染色，使得相邻节点不同色，来判定二分图。

我们可以通过 DFS 来实现。由于实现比较简单，此处不给出代码。

二分图最大匹配

有多个算法可以用来求二分图的最大匹配。

方便起见，下面我们约定，二分图的两个顶点集为 $U$ 和 $V$。

匈牙利算法

匈牙利算法是一个思想简单易懂的算法。

我们依次考虑 $U$ 中的点，尝试对其做匹配。设当前点为 $u$。

依次考虑和 $u$ 相连接的所有点，设考虑到了 $v$。如果 $v$ 没被匹配，就增加一个 $(u, v)$ 的匹配；否则，看能不能让和 $v$ 匹配的点（设为 $w$）和 $v$ 之外的点匹配。如果能，那就增加一个 $(u, v)$ 的匹配。可以看出，给 $w$ “找下家”的过程是可以和给 $u$ 找匹配一样递归去做的。

还有一个问题需要考虑，即对于同一个 $u$，所有的 $v$ 只能被使用一次（无论是对 $u$ 本身还是在时候递归的过程里），否则不能保证时间复杂度和程序正确性。事实上，如果 $v$ 已经被使用过了，那么就说明 $v$ 要么在递归的上层作为目标，要么已经被尝试“腾出位置”过而没有成功。无论是哪种情况都说明 $v$ 已经没有再被使用的意义。

下面给出一个简单的实现。其中 from 代表右边节点的匹配对象，vis 代表是否被使用过。

int match(int x){
    for (int i = at[x]; i; i = nxt[i]){
        int v = to[i];
        if (!vis[v]){
            vis[v] = true;
            if (!from[v] || match(from[v])){
                from[v] = x;
                return 1;
            }
        }
    }
    return 0;
}
void Hungary(){
    int match_size = 0;
    memset(from, 0, sizeof(from));
    for (int i = 1; i <= n; ++i){
        memset(vis, 0, sizeof(vis));
        match_size += match(i);
    }
}

可以看出，匈牙利算法的时间复杂度是 $O(|V||E|)$，一般不适用于数据量大的场合。但是在一种特殊情况下却很好用：如果要求的是二分图的最小字典序匹配（这里指的是按顺序比较 $U$ 中 1 号点，2 号点，等等匹配到的点的标号），只需要对匈牙利算法稍加改动即可。

改动的地方就是主程序中的循环顺序，只需要将下标（也就是点的标号）从大到小循环即可。为什么要这么做？直观的说，是因为这么做可以让 $U$ 中标号最小的点尽可能的匹配到标号小的点，也就是让 $U$ 中标号大的点尽可能腾位子给小的点。（具体证明待补充）

Hopcroft-Karp 算法（HK 算法）

HK 算法是一个基于匈牙利算法，但比其效率要高的算法。

HK 算法的优势在于它同时对一系列路径进行增广。在这里有多个数据需要维护：设 dx,dy 分别为 $U, V$ 两部分点的距离标号；mx，my 为 $U, V$ 两部分点的匹配对象。

每一轮，我们都将没被匹配的节点放入队列中，令这些点的距离标号为 0。然后对队列中的元素依次考虑，直到队列为空。设当前被考虑到的是 $u$。考虑 $u$ 的所有邻居，设当前为 $v$。

如果 $v$ 没有被匹配，那么表明存在增广路径。否则，将 $v$ 的匹配对象放入队列，以便后续检查是否有增广路径。无论哪种情况，都要对 $v$，以及可能存在的 $v$ 的匹配对象更新距离标号（如 d[v]:=d[u]+1）。

如果直到队列为空都没有出现增广路径就表明算法结束（用一个 flag 判断）。否则，对 $U$ 中所有没有匹配对象的点做一次匈牙利算法中的 match 操作。这里稍有不同的是，match 操作中只能使用距离相差为 1 的点，详细见代码。

和上面匈牙利算法一样，要考虑一个占用的问题，也就是说，$V$ 中的点不能同时在两条增广路径上。我们用 dy 数组标识 $V$ 中的点的占用情况，如果不为 0 就表明被占用。

int dx[3005], dy[3005], mx[3005], my[3005], n, m;
bool vis[3005];
queue<int> que;
vector<int> G[3005];
bool match(int x){
    for (int i = 0; i < G[x].size(); ++i){
        int v = G[x][i];
        if (!vis[v] && dy[v] == dx[x] + 1){
            vis[v] = true;
            if (!my[v] || match(my[v])){
                mx[x] = v, my[v] = x;
                return true;
            }
        }
    }
    return false;
}
int HK(){
    memset(mx, 0, sizeof(mx));
    memset(my, 0, sizeof(my));
    int ans = 0;
    for (; ; ){
        bool flag = false;
        while (!que.empty()) que.pop();
        memset(dx, 0, sizeof(dx));
        memset(dy, 0, sizeof(dy));
        for (int i = 1; i <= n; ++i)
            if (!mx[i]) que.push(i);
        while (!que.empty()){
            int u = que.front();
            que.pop();
            for (int i = 0; i < G[u].size(); ++i){
                int v = G[u][i];
                if (!dy[v]){
                    dy[v] = dx[u] + 1;
                    if (my[v]){
                        dx[my[v]] = dy[v] + 1;
                        que.push(my[v]);
                    }else flag = true;
                }
            }
        }
        if (!flag) break;
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; ++i)
            if (!mx[i] && match(i))
                ++ans;
    }
    return ans;
}

基于种种证明，HK 算法的时间复杂度为 $O(|E|\sqrt {|V|})$。

KM 算法

KM 算法用于求解最大完备匹配。

实际上 KM 算法的应用面比较窄，一般如果没有特殊要求还是用费用流求最大权匹配。