图的连通性

发表于 更新于

一、模板

0、关于代码的一些说明

对于第二个计算low值的地方 low[u] = min(low[u], dfn[v]), 对于新手可能会不小心写成low[u] = min(low[u], low[v]), 这样是不对的，考虑如下边构成的(无/有)向图:

1
2
3
4
5
1 3
2 3
3 4
3 5
4 5

如果写成low[u] = min(low[u], low[v])，判断割点的时候就会出错。

第二个说明点是，我们在求桥(割边)时，在有平行边的时候使用父节点号来判断反向边会出错，这里建议使用反向边判断：if (i == (fa ^ 1)) continue;。

1、Tarjan 求无向图的桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int maxn = 200100;
int dfn[maxn], low[maxn], tdf = 0;
struct Edge {
    int next, to;
} edges[maxn * 2];
int heads[maxn], pos = 1;

void addEdge(int a, int b) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}

// Tarjan 求无向图的桥
vector<vector<int>> ans;
void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++tdf;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (i == (fa ^ 1)) continue;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                // bridge u - v
                ans.push_back({u, v});
            }
        } else low[u] = min(low[u], dfn[v]);
    }
}

2、Tarjan无向图求割点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int maxn = 100100;
int dfn[maxn], low[maxn], tdf = 0;
int heads[maxn], pos = 0;
struct Edge {
    int next, to;
} edges[maxn * 2];

void addEdge(int a, int b) {
    //printf("edge: %d => %d\n", a, b);
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}
// 无向图求割点(割点无需判断反向边)
int cut[maxn];
void tarjan1(int u, bool root) {
    low[u] = dfn[u] = ++tdf;
    int cnt = 0;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (!dfn[v]) {
            tarjan1(v, false);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u])
                if (!root || ++cnt > 1) cut[u] = 1;
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

3、Tarjan无向图V-DCC缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int maxn = 100100;
struct Edge {
    int next, to;
} edges[maxn * 2];
int heads[maxn], pos = 1;

void addEdge(int a, int b) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}

// 无向图V-DCC
int dfn[maxn], low[maxn], tdf = 0;
int v_dcc_stk[maxn], v_dcc_sp = -1, cut[maxn];
vector<int> v_dcc_set[maxn];
int v_dcc_cnt = 0;
void tarjan(int u, bool root) {
    low[u] = dfn[u] = ++tdf; v_dcc_stk[++v_dcc_sp] = u;
    int cnt = 0;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (!dfn[v]) {
            tarjan(v, false);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                if (!root || ++cnt > 1) cut[u] = 1;
                v_dcc_set[v_dcc_cnt].clear();
                while (1) {
                    int z = v_dcc_stk[v_dcc_sp--];
                    v_dcc_set[v_dcc_cnt].push_back(z);
                    if (v == z) break;
                }
                v_dcc_set[v_dcc_cnt++].push_back(u);
            }
        }
        else low[u] = min(low[u], dfn[v]);
    }
}

4、Tarjan有向图SCC缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
const int maxn = 100010;
int heads[maxn], pos = 1;
struct Edge {
    int next, to;
} edges[maxn * 4];
void addEdge(int a, int b) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}
// 无向图求SCC
int dfn[maxn], low[maxn], tdf = 0;
int scc_instk[maxn];
int scc_stk[maxn], scc_sp = -1;
int scc[maxn], scc_size[maxn], scc_cnt = 0;
void tarjan(int u) {
    low[u] = dfn[u] = ++tdf;
    scc_stk[++scc_sp] = u, scc_instk[u] = 1;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (!dfn[v])
            tarjan(v),
            low[u] = min(low[u], low[v]);
        else if(scc_instk[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u]){
        int v; scc_size[++scc_cnt] = 0;
        do{
            v = scc_stk[scc_sp--];
            scc_instk[v] = 0;
            scc[v] = scc_cnt;
            ++scc_size[scc_cnt];
        }while(u != v);
    }
}

5、Tarjan无向图E-DCC缩点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

const int maxn = 500100;
int heads[maxn], pos = 1;
struct Edge {
    int next, to;
} edges[1000010 * 4];
void addEdge(int a, int b) {
    edges[++pos].next = heads[a];
    edges[pos].to = b;
    heads[a] = pos;
}
int dfn[maxn], low[maxn], tdf = 0;
int e_dcc[maxn], e_dcc_stk[maxn], e_dcc_cnt = 0, e_dcc_sp = -1;
void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++tdf; e_dcc_stk[++e_dcc_sp] = u;
    for (int i = heads[u]; i; i = edges[i].next) {
        int v = edges[i].to;
        if (i == (fa ^ 1)) continue;
        if (!dfn[v]) tarjan(v, i), low[u] = min(low[u], low[v]);
        else low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++e_dcc_cnt;
        while (1) {
            int v = e_dcc_stk[e_dcc_sp--];
            e_dcc[v] = e_dcc_cnt;
            if (u == v) break;
        }
    }
}