强连通分量

给定任意一个有向图，当我们找到它的所有强联通分量，把每个强联通分量都看成一个点，就能得到一个有向无环图(DAG)，从而简化问题

dfs生成树

首先我们介绍一下dfs生成树。如图:

dfs生成树是使用dfs算法对一个图进行搜索，搜索过程中经过的边的节点组成了这棵树。

有向图的 DFS 生成树主要有 4 种边(不一定全部出现):

• 树边（tree edge）：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边；
• 反祖边（back edge）：示意图中以红色边表示（即 \(7 \rightarrow 1\) ），也被叫做回边，即指向祖先结点的边；
• 横叉边（cross edge）：示意图中以蓝色边表示（即 \(9 \rightarrow 7\) ），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。；
• 前向边（forward edge）：示意图中以绿色边表示（即 \(3 \rightarrow 6\) ），它是在搜索的时候遇到子树中的结点的时候形成的。

如果结点 \(u\) 是某个强连通分量在dfs搜索过程中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 \(u\) 为根的子树中（而非子树中所有节点都是强连通分量中的节点）。结点 \(u\) 被称为这个强连通分量的根。

证明如下:

假设节点 \(v\) 在强连通分量中，但不在以 \(u\) 为根的子树中，那么 \(u\) 到 \(v\) 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 \(u\) 是第一个访问的结点矛盾了。

Tarjan算法

Tarjan算法为每个节点 \(u\) 维护两个变量:

1. \(dfn[u]\) : 表示这个节点被访问的时间。

2. \(low[u]\) : 两种理解

3. 从 \(u\) 沿着一条路径（不管路径上边的类型）能够走到最早的一个祖先，此时用 \(low[v]\)更新 \(low[u]\)

4. 从 \(u\) 的子树中每一个节点出发，再向前走一条非树边，能够走到最早的祖先，此时用 \(dfn[v]\) 更新 \(low[u]\)​

代码如下 :

for(auto v : adj[u]){
    // 判断节点v是否已经被访问了
    if(!dfn[v]){
        dfs(v);
        low[u] = min(low[u], low[v]);
    }
    //如果没有，就判断它是不是自己的父亲
    else{
        if(inSta[v]){
            low[u] = min(low[u], dfn[v]); // 写法1
            low[u] = min(low[u], low[v]); // 写法2
            //两种写法，第一种更普遍，两种效果近似相同，均可AC
        }
    }
}

接下来，我们讨论这两个变量和强连通分量之间的关系。

根据定义我们容易知道，如果一个节点的 \(dfn\) 和它的 \(low\) 值相等，那么它要么是一个孤立的点，要么一定可以通过至少一条路径回到自己，形成一个闭环，也就是一个强连通分量。如图 :

因此，对于强联通分量的根节点有 $$ dfn[u] = low[u] $$​

但是我们要想找到某个强联通分量里的所有节点，不可以直接记录子树内的所有节点，而是使用栈：每当发现一个新的节点，就把它入栈；每当找到一个强联通分量，就把栈里其上面的所有节点都弹出来记录答案。

例题

B3609 [图论与代数结构 701] 强连通分量

Tarjan 模板题

Tarjan 算法过程

• 全局定义一个栈 \(s\)；
• 递归算法，当递归到 \(u\) 点时候，首先把 \(u\) 进栈，并设 \(low[u]=pre[u]\) ，然后去遍历u的出边到v；
• 如果发现 \((u,v)\) 是树边，那么递归 \(v\) 点，然后从 \(v\) 点递归回来以后，用 \(low[v]\) 去更新 \(low[u]\)。
• 如果发现 \(v\) 还没有被标记归属于某个已知的 SCC，那么 \(u\) 就可能和 \(v\) 在一个 SCC 中，故此时用 \(pre[v]\) 更新 \(low[u]\)。
• 当即将离开u点的时候，发现 \(low[u]=pre[u]\) ，那么 \(u\) 就是这个 SCC 的第一个点，这时候栈里面 \(u\) 后面的所有点都属于这个 SCC。

代码

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int N = 10010;

int n, m, tm, cnt;
int dfn[N], low[N], col[N], inSta[N], vis[N];
vector<int> adj[N];
stack<int> sta;

// 快读
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

// Tarjan
void dfs(int u){

    // 入栈
    sta.push(u);
    inSta[u] = 1;
    low[u] = dfn[u] = ++tm;
    for(auto v : adj[u]){
        if(!dfn[v]){
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else{
            if(inSta[v]){
                low[u] = min(low[u], pre[v]);
            }
        }
    }

// 判断是不是强连通分量
    if(dfn[u] == low[u]){
// 记录这个节点和这个颜色并出栈
        col[u] = ++cnt;
        inSta[u] = 0;
// 弹出所有栈顶元素，它们同时也是强连通分量里的节点
        while(sta.top() != u){
            col[sta.top()] = cnt;
            inSta[sta.top()] = 0;
            sta.pop();
        }
        sta.pop();
    }
}

int main(){

    n = read();
    m = read();
    for(int i = 1; i <= m; i++){
        int u = read();
        int v = read();
        adj[u].push_back(v);
    }

// 要考虑非连通图的情况，循环一遍
    for(int i = 1; i <= n; i++){
        if(dfn[i] == 0) dfs(i);
    }

    cout << cnt << endl;

    for(int i = 1; i <= n; i++){
        if(vis[i] == 0){
            for(int j = i; j <= n; j++){
                if(col[j] == col[i]){
                    cout << j << ' ';
                    vis[j] = 1;
                }
            }
            cout << endl;
        }
    }

    return 0;
}

P2863 [USACO06JAN] The Cow Prom S

代码

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N = 2E4 + 10;

int n, m, dt, sccCnt, ans;
int sccNo[N], sz[N], pre[N], low[N];
vector<int> adj[N];
stack<int> sta;

void tarjan(int u){

    low[u] = pre[u] = ++dt;
    sta.push(u);
    for(auto v : adj[u]){
        if(pre[v] == 0){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(sccNo[v] == 0){
            low[u] = min(low[u], pre[v]);
        }
    }
    if(low[u] == pre[u]){
        sccNo[u] = ++sccCnt;
        while(sta.top() != u){
            sccNo[sta.top()] = sccCnt;
            sta.pop();
        }
        sta.pop();
    }

}

int main(){

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for(int i = 1; i <= n; i++){
        if(sccNo[i] == 0) tarjan(i);
    }

    for(int i = 1; i <= n; i++){
        sz[sccNo[i]]++;
    }
    for(int i = 1; i <= sccCnt; i++){
        if(sz[i] > 1) ans++;
    }
    cout << ans << endl;

    return 0;
}

U102242 Proving Equivalences

结论/引理:

在一个 DAG中，入度为 \(0\) 的点有 \(a\) 个，出度为 \(0\) 的点有 \(b\) 个，那么最少添加 \(max(a,b)\) 条边就可以让该 DAG 变成一个强连通图。

解题思路:

• 用 tarjan 计算强连通分量，缩点 • 在形成的分量图中，尽量添加最少的边，使得新图强连通。设有 \(a\) 个结点入度为 \(0\)，\(b\)个结点出度为 \(0\)，则 \(max(a,b)\) 是答案。特殊情况，如果新图已经强连通了，答案是 \(0\)，需要特判。

代码

#include<iostream>
#include<stack>
#include<cstring>
#include<vector>
using namespace std;
const int N = 2E4 + 10;

int t;
int n, m;
vector<int> adj[N];
stack<int> sta;

int dt, sccCnt;
int pre[N], low[N], sccNo[N];
void tarjan(int u){

    sta.push(u);
    low[u] = pre[u] = ++dt;
    for(auto v : adj[u]){
        if(!pre[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(!sccNo[v]){
            low[u] = min(low[u], pre[v]);
        }
    }
    if(low[u] == pre[u]){
        sccNo[u] = ++sccCnt;
        while(sta.top() != u){
            sccNo[sta.top()] = sccCnt;
            sta.pop();
        }
        sta.pop();
    }

}

int noIn, noOut;
bool ind[N], otd[N];
int main(){

    cin >> t;
    while(t--){
        cin >> n >> m;
        sccCnt = dt = 0;
        noIn = noOut = 0;
        memset(sccNo, 0, sizeof(sccNo));
        memset(pre, 0, sizeof(pre));
        memset(otd, 0, sizeof(otd));
        memset(ind, 0, sizeof(ind));
        for(int i = 1; i <= n; i++){
            adj[i].clear();
        }
        for(int i = 1; i <= m; i++){
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
        }
        for(int i = 1; i <= n; i++){
            if(!sccNo[i]) tarjan(i);
        }
        for(int u = 1; u <= n; u++){
            for(auto v : adj[u]){
                if(sccNo[u] == sccNo[v]) continue;
                otd[sccNo[u]] = 1;
                ind[sccNo[v]] = 1;
            }
        }
        for(int i = 1; i <= sccCnt; i++){
            if(otd[i] == 0) noOut++;
            if(ind[i] == 0) noIn++;
        }
        if(sccCnt == 1) cout << 0 << endl;
        else cout << max(noIn, noOut) << endl;
    }

    return 0;
}

P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

解题思路:

在缩点形成的 DAG 中，如果有大于一个点（其实是一个强连通分量）的出度是0，那么就没有任何一头奶牛是明星，因为一个（群）出度为 \(0\) 的奶牛并不喜欢另一个（群）出度为 \(0\) 的奶牛。

代码

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
const int N = 1E4 + 10;

int n, m;
vector<int> adj[N];
stack<int> sta;

int dt, sccCnt;
int pre[N], low[N], sccNo[N], sccSz[N];

void tarjan(int u){

    sta.push(u);
    low[u] = pre[u] = ++dt;
    for(auto v : adj[u]){
        if(!pre[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(!sccNo[v]){
            low[u] = min(low[u], pre[v]);
        }
    }
    if(low[u] == pre[u]){
        sccNo[u] = ++sccCnt;
        sccSz[sccCnt]++;
        while(sta.top() != u){
            sccNo[sta.top()] = sccCnt;
            sta.pop();
            sccSz[sccCnt]++;
        }
        sta.pop();
    }
}

int otd[N], noOut;
int main(){

    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for(int i = 1; i <= n; i++){
        if(!sccNo[i]) tarjan(i);
    }

    for(int u = 1; u <= n; u++){
        for(auto v : adj[u]){
            if(sccNo[u] == sccNo[v]) continue;
            otd[sccNo[u]]++;
        }
    }

    for(int i = 1; i <= sccCnt; i++){
        if(otd[i] == 0){
            if(noOut){
                cout << 0 << endl;
                return 0;
            }
            noOut = i;
        }
    }

    cout << sccSz[noOut] << endl;

    return 0;
}

P2746 [USACO5.3] 校园网Network of Schools

结论/引理:

在一个DAG中，从所有入度为0的点出发可以到达所有点。

代码

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int N = 105;

int n;
vector<int> adj[N];
stack<int> sta;

int dt, sccCnt;
int pre[N], low[N], sccNo[N];
void tarjan(int u){

    sta.push(u);
    low[u] = pre[u] = ++dt;
    for(auto v : adj[u]){
        if(pre[v] == 0){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(sccNo[v] == 0){
            low[u] = min(low[u], pre[v]);
        }
    }
    if(low[u] == pre[u]){
        sccNo[u] = ++sccCnt;
        while(sta.top() != u){
            sccNo[sta.top()] = sccCnt;
            sta.pop();
        }
        sta.pop();
    }

}

bool ind[N], otd[N];
int noIn, noOut;
int main(){

    cin >> n;
    for(int u = 1; u <= n; u++){
        while(true){
            int v;
            cin >> v;
            if(v == 0) break;
            adj[u].push_back(v);
        }
    }

    for(int i = 1; i <= n; i++){
        if(sccNo[i] == 0) tarjan(i);
    }

    for(int u = 1; u <= n; u++){
        for(auto v : adj[u]){
            if(sccNo[u] == sccNo[v]) continue;
            ind[sccNo[v]] = 1;
            otd[sccNo[u]] = 1;
        }
    }

    for(int i = 1; i <= sccCnt; i++){
        if(ind[i] == 0) noIn++;
        if(otd[i] == 0) noOut++;
    }

    if(sccCnt == 1) cout << 1 << endl << 0 << endl;
    else cout << noIn << endl << max(noIn, noOut) << endl;

    return 0;
}