DDOSvoid's Blog

tarjan

发表于 更新于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

简介

本文涵盖以下内容：

  1. 缩点
  2. 割点
  3. 点双连通分量
  4. 边双连通分量

缩点

定义

如果有向图G中的任何两个顶点都可以互相到达，则称图G为强连通图。如果图G不是强连通图，他的子图G'是强连通图，则称图G'为图G的强连通分量

算法

缩点最经典的算法自然是tarjan（我觉得直接拿名字命名其实挺好的

稍微讲一下原理

首先tarjan本质上是一个dfs

那么我们肯定能得到一棵dfs树

但是原图是一张有向图，所以除了树边还有两种边

第一种是连向自己的祖先的边，我们称之为回边

第二种是连向之前已经到达且没有祖先关系的点，我们称之为横叉边

我们考虑什么情况下会形成强连通分量

显然是回边所连成的一个环为一个强连通分量，而横叉边对强连通分量没有任何影响

然后，实现就看代码吧 = =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dfn[maxn], low[maxn], bl[maxn], scc, W[maxn];
bool ins[maxn]; stack<int> S; 
void tarjan(int u) { 
    static int cnt = 0; 
    dfn[u] = low[u] = ++cnt; ins[u] = 1; S.push(u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        int t; ++scc;
        do { 
        	t = S.top(); S.pop(); 
           	bl[t] = scc;
        } while (t != u);
    }
}

割点

定义

若删除某点后，原连通图分割成多个子图，则称该点为割点

算法

注意根节点要特判

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dfn[maxn], low[maxn]; bool ans[maxn]; 
void tarjan(int u, int fa) {
    static int cnt = 0; 
    dfn[u] = low[u] = ++cnt; int du = 0; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue; 
        if (!dfn[v]) { ++du; 
            tarjan(v, u); low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] && fa) ans[u] = 1;
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if (!fa && du > 1) ans[u] = 1; 
}

点双连通分量

定义

定义1：若一个无向图中去掉任意一个节点都会改变此图的连通性，即不存在割点，则称此图为点双连通图。

定义2：若一个无向图任意两点存在两条点不相交的路径，则称此图为点双连通图。

一个无向图的每一个极大点双连通子图称为此图的一个点双连通分量（两个点一条边也算

性质

  1. 一个点双里可能有多个原图中的割点
  2. 点双之间以割点连接，且两个点双间有且仅有一个割点
  3. 只有一条边连通的两个点也是一个点双连通分量（定义2中不成立，定义1中成立
  4. 点双缩点之后得到一棵树，每个树边代表两个点双之间的割点，也就是说树上的点的度数为多少就代表这个点双内有多少割点，当然我们如果在缩点的时候加一些其它操作就能得到圆方树

算法

注意这个算法会将只有一条边连通的两个点也当成一个点双

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int dfn[maxn], low[maxn], dcc; bool ist[maxn];  
vector<int> A[maxn]; stack<int> S;
void tarjan(int u, int fa) {
    static int cnt = 0; 
    dfn[u] = low[u] = ++cnt; S.push(u); int du = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue; 
        if (!dfn[v]) { ++du;
            tarjan(v, u); low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ++dcc; int t; 
                do {
                    t = S.top(); S.pop();
                    A[dcc].push_back(t);
                } while (t != v);
                A[dcc].push_back(u);
                if (fa) ist[u] = 1; 
            }
        }
        else low[u] = min(low[u], dfn[v]); 
    } if (!fa && du > 1) ist[u] = 1; 
}

获得一个点双的所有边的方法

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
int dfn[maxn], low[maxn], c2, dcc, bl[maxn];
stack<int> S, E; vector<int> A[maxn];
void tarjan(int u, int fa) {
    static int cnt = 0; 
    dfn[u] = low[u] = ++cnt; S.push(u);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, ext = e[i].ext; if (v == fa) continue;
        int cur = E.size(); 
        if (!ext) E.push(i), ext = e[i ^ 1].ext = 1; 
        if (!dfn[v]) {
            tarjan(v, u); low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {
                ++dcc; int t; 
                do {
                    t = S.top(); S.pop();
                    A[dcc].push_back(t);
                } while (t != v);
                A[dcc].push_back(u);
                while (E.size() > cur) {
                    bl[E.top()] = dcc;
                    E.pop();
                } 
            }
        }
        else low[u] = min(low[u], dfn[v]); 
    }
}

边双连通分量

定义

一个无向图任意两点存在两条边不相交的路径，则称此图为边双连通图。

一个无向图的每一个极大边双连通子图称为此图的一个边双连通分量

性质

  1. 桥不属于任何一个边双
  2. 把所有桥删掉，图会被分为若干连通块，每一个连通块就是一个边双

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void tarjan(int u, int fa) {
    static int cnt = 0;
    dfn[u] = low[u] = ++cnt; S.push(u); 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, &f1 = e[i].f, &f2 = e[i ^ 1].f; if (v == fa) continue;
        if (!dfn[v]) {
            tarjan(v, u), low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) f1 = f2 = 1; 
        }
        else low[u] = min(low[u], dfn[v]); 
    }
    if (low[u] == dfn[u]) {
        int t;
        do {
            t = S.top(); S.pop();
            ++sum; 
        } while (t != u);
    }
}

例题

  1. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向连通图，求最少加多少条双向边使得该无向图可以变成边双连通图

    $n\le 5000,m\le 10000$

    简要题解：边双缩点之后得到一棵树，将这棵树变成边双只需要将度数为 $1$ 的点都连起来

    答案为 $(ans + 1) / 2$ ，$ans$ 是叶子节点的个数

    Luogu P2860 [USACO06JAN]Redundant Paths G

  2. 简要题意：给定一个 $n$ 个点 $m$ 条边的有向无环图，求最少加多少条边使原图变成强连通图

    $n\le 2\times 10^4,m\le 5\times 10^5$

    简要题解：将一个 $DAG$ 变成一个强连通图最少加边为 $max \{ \sum {in[u] =0},\sum{out[u]=0} \}$

    所以我们直接缩点统计一下入度和出度就行，注意到我们不需要判断重边

    另外该结论有一个特例，就是当 $ DAG $ 只有一个点时，答案应该为 $0$，特判一下即可

    hdu 2767 Proving Equivalences

  3. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，现在需要给所有边定向，使得所有点的 $R_i$ 的最小值最大，$R_i$ 表示从点 $i$ 出发能够到达的点的个数

    $n,m\le 4\times 10^5$

    简要题解：需要注意到有两个性质

    1. 边双连通分量一定可以通过给边定向变成强连通分量
    2. 树的 $R_i$ 的最小值为 $1$

    $2$ 很好理解，对于 $1$ 我们考虑求边双的过程，树边方向向下，回边方向向上即可

    我们考虑边双缩点之后形成一棵树，我们以最大的边双为根，然后树边都从儿子连到父亲

    那么 $R_i$ 的最小值就是最大的边双

    CF 732F Tourist Reform

  4. 简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向连通图，边有边权，边权要么为 $0$，要么为 $1$。每条边只能通过一次（两个方向加起来只能通过一次）。求是否存在一条从 $a$ 到 $b$ 的路径，满足路径上至少存在一条权为 $1$ 的边。

    简要题解：注意到每条边只能选择一个方向走

    那么对于一个边双，我们能够将边双里的边都走完

    我们考虑将原图缩点变成一棵树，那么如果从 $s$ 到 $t$ 的路径上有边双内部有 $1$ 或者路径上的割边有 $1$，则一定存在至少有一个 $1$ 的路径

    CF 652E Pursuit For Artifacts

  5. 简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，求恰好被包含在一个简单环中的边

    $n,m\le 10^5$

    简要题解：注意到一个简单环就是一个双连通分量,这时候我们要考虑使用边双还是点双

    如果两个简单环只有一个交点，那么这两个简单环是独立的

    所以我们使用点双，因为边双内可能有多个独立的简单环

    对于一个点双，如果点数等于边数，那么这个点双就是一个简单环

    所以我们只需要统计点数等于边数的点双即可

    CF 962F Simple Cycles Edges