强连通分量

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

err-tag

例题 1

给定一个有向图，判断是否对于任意无向点对 \((x,y)\) 都要么可以从 \(x\) 走到 \(y\)，要么可以从 \(y\) 走到 \(x\)。

注意到一个 SCC 可以视为一个节点，剩下部分形成一个 DAG。注意到题目限制等价于 DAG 传递闭包的最长反链等于 \(1\)，根据 Dilworth 定理，其最小链覆盖等于 \(1\)，即该 DAG 就是一条链。

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;
}