有向图的强连通分量

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

有向图的强连通分量

作者：

lhqwd , 2021-03-09 16:03:25 , 所有人可见 , 阅读 315

有向图的强连通分量

连通分量:

对于分量内任意两点$u 和 v$ , 必然可以找到从 $u$ 走到 $v$ 且可以从 $v$ 走到 $u$.

强连通分量:

极大连通分量(包含点数最多)

强连通分量常用于缩点

Tarjan算法:

基于 $DFS$ :

Tarjan算法几个重要概念:

在已经$DFS$的树中:

后前边: (x, y) x是y的一个祖先, 但存在一条由y->x的边.
横插边: (x, y) x和y不属于同一条分支, 但存在一条y->x的边
前向边: (x, y) y是x的祖先, 存在一条x->y的边

几个数组和变量:

时间戳: 记录搜索到每个点的时间.即对每个点根据搜索顺序进行标号排序.
dfn数组: 记录每个点的时间戳.(同时具有判重数组作用)
low数组: 记录每个点向上走所能达到的最高点(即时间戳最小点).
stk栈: 记录当前强连通分量内的点.
id数组: 记录每个点所在的连通分量.
scc_cnt: 强连通分量个数

模板:

int timecnt;            //时间戳
int dfn[N];             //每个点的时间戳
int low[N];             //low[u] : u所在的子树中所有点中所能向上走到的时间戳最小的点
int scc_cnt;            //强连通分量的数量
int id[N];              //id[i] : 表示i号点所在的强连通分量的编号
stack<int> stk;         //存储当前强连通分量里的所有点
int in_stk[N];          //记录该点是否在栈中

void tarjan(int u)
{
    low[u] = dfn[u] = ++ timecnt;
    stk.push(u);
    in_stk[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){               //j点没有被遍历过,j点一定是在子树中

            tarjan(j);              //遍历j
            low[u] = min(low[u], low[j]);       //遍历过后的j的low可能已经找到一个更高的结点,所以要去更新u

        }
        else if (in_stk[j])         //j在栈中,则j和u之间一定是一条横叉边或向前边,即j的时间戳一定比u小
            low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]){          //到此处,u的所有边已经遍历完,如果low[u] = dfn[u] : 得到了一个强连通分量
        scc_cnt ++;
        int y;                      //此时该强连通分量里的点全在栈中,全部取出
        do{
            y = stk.top();
            stk.pop();
            id[y] = scc_cnt;
            sizes[scc_cnt] ++;
        }while (y != u);
    }

}

AcWing 1174. 受欢迎的牛原题链接

算法思路 :

强连通分量的典型应用:缩点. 将整个图缩点后,得到一张拓扑图, 求出强连通分量后, 寻找出度为0的节点, 该节点内的牛的数量为答案(注意出度为0的点只能有一个,否则结果为0)

#include <iostream>
#include <cstring>
#include <queue>
#include <stack>

using namespace std;

const int N = 1e5 + 10, M = 5e4 + 10;

int h[N], e[M], ne[M], idx;

int timecnt;            //时间戳
int dfn[N];             //每个点的时间戳
int low[N];             //low[u] : u所在的子树中所有点中所能向上走到的时间戳最小的点
int scc_cnt;            //强连通分量的数量
int id[N];              //id[i] : 表示i号点所在的强连通分量的编号
stack<int> stk;         //存储当前强连通分量里的所有点
int in_stk[N];          //记录该点是否在栈中

int sizes[N];            //强连通分量的结点数量
int dout[N];            //每个强连通分量的出度
int n, m;

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

void tarjan(int u)
{
    low[u] = dfn[u] = ++ timecnt;
    stk.push(u);
    in_stk[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){               //j点没有被遍历过,j点一定是在子树中

            tarjan(j);              //遍历j
            low[u] = min(low[u], low[j]);       //遍历过后的j的low可能已经找到一个更高的结点,所以要去更新u

        }
        else if (in_stk[j])         //j在栈中,则j和u之间一定是一条横叉边或向前边,即j的时间戳一定比u小
            low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]){          //到此处,u的所有边已经遍历完,如果low[u] = dfn[u] : 得到了一个强连通分量
        scc_cnt ++;
        int y;                      //此时该强连通分量里的点全在栈中,全部取出
        do{
            y = stk.top();
            stk.pop();
            id[y] = scc_cnt;
            sizes[scc_cnt] ++;
        }while (y != u);
    }

} 


int main()
{
    cin >> n >> m;

    memset (h, -1, sizeof h);

    for (int i = 1; i <= m; i ++ ){
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

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

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j]){
            int k = e[j];

            int a = id[i], b = id[k];
            if (a != b){                //二者不在同一个强连通分量内,则由i -> k的边是缩点后点一条边,对于连通分量: a -> b
                dout[a] ++;
            }
        }

    int cnt = 0;
    int sum = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (!dout[i]){
            cnt ++;
            sum = sizes[i];
            if (cnt > 1){
                sum = 0;
                break;
            }
        }

    cout << sum << endl;

    return 0;
}

AcWing 367. 学校网络原题链接

算法思路:

强连通分量缩点, 将原图转化为拓扑图, 第一问求入度为0的点的个数, 第二问结论: $ max(cnt_{in}, cnt_{out})$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

const int N = 110, M = N * N / 2;

int h[N], e[M], ne[M], idx;

int timecnt;
int low[N], dfn[N];
stack<int> stk;
int scc_cnt;
int id[N];
int in_stk[N];
int dout[N];
int din[N];

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++timecnt;
    stk.push(u);
    in_stk[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }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();
            stk.pop();
            in_stk[y] = 0;
            id[y] = scc_cnt;

        }while (y != u);
    }

}

int main()
{
    int n;
    cin >> n;
    memset (h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ){
        int b;
        while (cin >> b && b){
            add(i, b);
        }
    }

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

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j]){
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b){
                dout[a] ++;
                din[b] ++;
            }
        }

    int in_cnt = 0;
    int out_cnt = 0;
    for (int i = 1; i <= scc_cnt; i ++ ){
        if (!dout[i]){
            out_cnt ++;
        }
        if (!din[i]){
            in_cnt ++;
        }
    }

    if (scc_cnt == 1)
        cout << 1 << endl <<  0 << endl;
    else
        cout << in_cnt << endl << max(in_cnt, out_cnt) << endl;

    return 0;

}

AcWing 1175. 最大半连通子图原题链接

算法思路:(补)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <stack>

using namespace std;

const int N = 1e5 + 10, M = 2 * 1e6 + 10;
typedef long long LL;
int h[N], hs[N], e[M], ne[M], idx;

int timecnt;
int dfn[N], low[N];
stack<int> stk;
int scc_cnt;
int in_stk[N];
int sizes[N];
int id[N];

int f[N], g[N];
unordered_set<LL> used;
int n, m, mod;

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++timecnt;

    stk.push(u);
    in_stk[u] = 1;

    for (int i = h[u]; i != -1; i = ne[i]){
        int j = e[i];

        if (!dfn[j]){
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }else if (in_stk[j])
                low[u] = min(low[u], dfn[j]);
    }

    if (low[u] == dfn[u]){
        scc_cnt ++;
        int y;
        do{
            y = stk.top();
            stk.pop();
            in_stk[y] = 0;
            id[y] = scc_cnt;
            sizes[scc_cnt] ++;
        }while (y != u);
    }

}

int main()
{
    cin >> n >> m >> mod;
    memset (h, -1, sizeof h);
    memset (hs, -1, sizeof hs);

    for (int i = 1; i <= m; i ++ ){
        int a, b;
        scanf("%d%d",&a, &b);
        add(h, a, b);
    }

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

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; j != -1; j = ne[j]){
            int k = e[j];

            int a = id[i], b = id[k];
            if (a != b && !used.count((LL)a * 1e6 + b)){
                add(hs, a, b);
                used.insert((LL)a * 1e6 + b);
            }
        }

    for (int i = scc_cnt; i ; i -- ){
        if (!f[i]){
            f[i] = sizes[i];
            g[i] = 1;
        }
        for (int j = hs[i]; j != -1; j = ne[j]){
            int k = e[j];
            if (f[k] < f[i] + sizes[k]){
                f[k] = f[i] + sizes[k];
                g[k] = g[i];
            }else if (f[k] == f[i] + sizes[k])
                    g[k] = (g[k] + g[i]) % mod;
        }
    }

    int maxn = 0;
    int sum = 0;

    for (int i = 1; i <= scc_cnt; i ++ )
        if (f[i] > maxn){
            maxn = f[i];
            sum = g[i];
        }else if (f[i] == maxn)
            sum = (g[i] + sum) % mod;

    cout << maxn << endl << sum << endl;

    return 0;
}