c

casperwu

V1

2022/07/09阅读:21主题:凝夜紫

有向图的强连通分量

有向图的强连通分量

1 什么是连通分量

在一个有向图中, 对于分量中的任意的两个点 x 和 y, 既存在从 x 到 y 的路径, 也存在从 y 到 x 的路径。

连通分量可以简单的理解为: 一个有向图中存在环,每个环都是该图的一个连通分量。

强连通分量: 极大连通分量,即最大的环。

2 连通分量的作用

可以将一个有向图通过缩点的方式转换为一个有向无环图(DAG)。

3 模板题目

受欢迎的牛
受欢迎的牛

3.1 题意理解

通过阅读理解,可以将题意等价与找到被其他所有牛都欢迎的牛的数量。

转换为图论来思考,就等价于所有的点都可以走到当前这个点。如果使用暴力做的话, 对于每个点都要dfs或者bfs一次, 看是否所有点都可以到达该点,从某个点遍历一次的 时间复杂度是O(n + m),共有n个点, 因此时间复杂度是O(n(n+m)), 会超时。

优化的解法: 如果可以将图转换为拓扑图的话(DAG),就好解决了。因为只需要统计出度为 0 的点的数量,如果出度为0的点的数量 > 1,那么一定不存在最受欢迎的牛,此种情况等价于拓扑图 存在两个以上的终点,即存在终点1无法到达终点2,也就是不存在最受欢迎的牛。

如果出度为0的点的数量 = 1,则最终受欢迎的牛的个数就是该终点这个强连通分量中点的个数。

3.2 代码模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e4 + 4, M = 5e4 + 4;

int h[N], e[M], ne[M], idx;
// dfn[]用于存储当前点的时间戳, low[]存储当前点可以到的时间戳的最小值
int dfn[N], low[N], timestamp;
// 将当前前点入栈, 以及是否还在栈中
int stk[N], top;
bool in_stk[N];
// id[]记录某个点属于哪个连通分量, scnt记录连通分量中点的个数.
int id[N], cnt[N], scc_cnt;
// 记录点的出度
int dout[N];

int n, m;

void add(int a, int b) {
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}

void tarjin(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[top++] = u, in_stk[u] = true;
    
    for(int i = h[u]; i; i = ne[i]) {
        int j = e[i];
        
        if(!dfn[j]) {
            tarjin(j);
            low[u] = min(low[j], low[u]);
        } else if(in_stk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    
    if(dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do {
            y = stk[--top];
            id[y] = scc_cnt;
            cnt[scc_cnt]++;
        } while(y != u);
    }
}

int main() {
    cin >> n >> m;
    
    while(m--) {
        int a, b; cin >> a >> b;
        add(a, b);
    }
    
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjin(i);
    }
    
    for(int i = 1; i <= n; i++) {
        for(int j = h[i]; j; j = ne[j]) {
            int k = e[j];
            
            int a = id[i], b = id[k];
            if(a != b) {
                dout[a]++;
            }
        }
    }
    
    // sum 记录总数, zeros 记录出度为0的点的个数
    int sum = 0, zeros = 0;
    for(int i = 1; i <= scc_cnt; i++) {
        if(!dout[i]) {
            zeros++;
            sum += cnt[i];
            
            if(zeros > 1) {
                sum = 0;
                break;
            }
        }
    }
    
    cout << sum;
    return 0;
}

分类:

后端

标签:

C++

作者介绍

c
casperwu
V1