tarjan【桥、割点、点双、边双、支配树】 Summary

知识点总结

定义

1. 割点：若删掉某点后，原连通图分裂为多个子图，则称该点为割点。

2. 割点集合：在一个无向连通图中，如果有一个顶点集合，删除这个顶点集合，以及这个集合中所有顶点相关联的边以后，原图变成多个连通块，就称这个点集为割点集合。

3. 点连通度：最小割点集合中的顶点数。

1. 割边(桥)：删掉它之后，图必然会分裂为两个或两个以上的子图。

2. 割边集合：如果有一个边集合，删除这个边集合以后，原图变成多个连通块，就称这个点集为割边集合。

3. 边连通度：一个图的边连通度的定义为，最小割边集合中的边数。

4. 缩点：把没有割边的连通子图缩为一个点，此时满足任意两点之间都有两条路径可达。

5. 双连通分量：分为点双连通和边双连通。它的标准定义为：点连通度大于1的图称为点双连通图，边连通度大于1的图称为边双连通图。通俗地讲，满足任意两点之间，能通过两条或两条以上没有任何重复边的路到达的图称为双连通图。无向图G的极大双连通子图称为双连通分量。

求解方法

1.求强连通分量、割点、桥、缩点： 对于Tarjan算法中，我们得到了dfn和low两个数组， low[u]=min(low[u],dfn[v])——(u,v)为后向边，v不是u的子树； low[u]=min(low[u],low[v])——(u,v)为树枝边，v为u的子树； 下边对其进行讨论： 若low[v]>=dfn[u],则u为割点，u和它的子孙形成一个块。 因为这说明u的子孙不能够通过其他边到达u的祖先， 这样去掉u之后，图必然分裂为两个子图。 若low[v]>dfn[u],则(u,v)为割边。理由类似于上一种情况。 2.求双连通分量以及构造双连通分量： 对于点双连通分量，实际上在求割点的过程中就能顺便把每个点双连通分量求出。 建立一个栈，存储当前双连通分量，在搜索图时，每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中。 如果遇到某时满足DFS(u)<=Low(v)，说明u是一个割点，同时把边从栈顶一个个取出， 直到遇到了边(u,v)，取出的这些边与其关联的点，组成一个点双连通分量。 割点可以属于多个点双连通分量，其余点和每条边只属于且属于一个点双连通分量。 对于边双连通分量，求法更为简单。只需在求出所有的桥以后，把桥边删除，原图变成了多个连通块，则每个连通块就是一个边双连通分量。 桥不属于任何一个边双连通分量，其余的边和每个顶点都属于且只属于一个边双连通分量。

Problem

hdu4378 Caocao's Bridges

Description

求权值最小的桥，特判如果最小桥值为0，则输出1

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1000000 + 10;

int Ans;
int N, M;
int A[1010][1010];
int P[1010][1010];
int e, Begin[Maxn], To[Maxn * 2], Next[Maxn * 2];
int dfn[Maxn], low[Maxn], Index;

inline void tarjan (int x, int fa)
{
    dfn[x] = low[x] = ++Index;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa) continue;
        if (!dfn[y])
        {
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if (dfn[x] < low[y] && !P[x][y])
                Ans = min(Ans, A[x][y]);
        }
        else
            low[x] = min(low[x], dfn[y]);
    }
}

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (scanf("%d%d", &N, &M) != EOF)
    {
        if (!N && !M) break;
        Index = 0;
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                A[i][j] = INT_MAX;
        memset(dfn, 0, sizeof(dfn));
        memset(P, 0, sizeof(P));
        memset(Begin, 0, sizeof(Begin));
        Ans = INT_MAX;
        for (int i = 1; i <= M; ++i)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            add_edge (x, y);
            add_edge (y, x);
            if (A[x][y] != INT_MAX) P[x][y] = P[y][x] = 1;
            A[x][y] = A[y][x] = min(A[x][y], z);
        }

        int fl = 0;
        for (int i = 1; i <= N; ++i)
            if (!dfn[i])
            {
                if (i != 1)
                {
                    fl = 1;
                    break;
                }
                tarjan(i, 0);
            }

        if (fl) cout<<0<<endl;
        else if (Ans == INT_MAX) cout<<-1<<endl;
        else if (!Ans) cout<<1<<endl;
        else cout<<Ans<<endl;
    }
    return 0;
}

hdu3394 Railway

Description

求桥的数量以及点双中 边数比点数多的边数之和

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>

using namespace std;

const int Maxn = 100000 + 100;

int Ans1, Ans2;
int N, M;
int e, Begin[Maxn], To[Maxn * 2], Next[Maxn * 2];
int dfn[Maxn], low[Maxn], Index;
int Vis[Maxn];
int BCC[Maxn];

stack <int> S;

inline void Calc ()
{
    memset(Vis, 0, sizeof(Vis));
    for (int i = 1; i <= BCC[0]; ++i) Vis[BCC[i]] = 1;
    int Cnt = 0;
    for (int i = 1; i <= BCC[0]; ++i)
    {
        for (int j = Begin[BCC[i]]; j; j = Next[j])
        {
            if (Vis[To[j]])
                Cnt ++;
        }
    }
    Cnt /= 2;
    if (Cnt > BCC[0]) Ans2 += Cnt;
}

inline void tarjan (int x, int fa)
{
    dfn[x] = low[x] = ++Index;
    S.push(x);
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa) continue;
        if (!dfn[y])
        {
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if (dfn[x] <= low[y])
            {
                if (dfn[x] < low[y])
                    ++Ans1;
                memset(BCC, 0, sizeof(BCC));
                while (1)
                {
                    int a = S.top(); S.pop();
                    BCC[++BCC[0]] = a;
                    if (a == y) break;
                }
                BCC[++BCC[0]] = x;
                Calc();
            }
        }
        else
            low[x] = min(low[x], dfn[y]);
    }
}

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

int main()
{
#ifdef hk_cnyali
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
#endif
    while (scanf("%d%d", &N, &M) != EOF)
    {
        e = 0;
        if (!N && !M) break;
        Index = 0;
        memset(dfn, 0, sizeof(dfn));
        memset(Begin, 0, sizeof(Begin));
        while (!S.empty()) S.pop();
        Ans1 = Ans2 = 0;
        for (int i = 1; i <= M; ++i)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            ++x, ++y;
            add_edge (x, y);
            add_edge (y, x);
        }

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

        cout<<Ans1<<" "<<Ans2<<endl;
    }
    return 0;
}

hdu2460 Network

Description

给出一个无向图以及Q次询问，每次询问增加一条无向边，要求输出增加这条边后剩余的桥的数目

Solution

先求桥的数量，然后每次询问暴力跳LCA就能过

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 400000 + 10;

int N, M;
int Ans, Vis[Maxn];
int e, Begin[Maxn], To[Maxn], Next[Maxn], f[Maxn];
int fa[Maxn];
int dfn[Maxn], low[Maxn], Index;

inline void add_edge (int x, int y)
{
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    f[e ++ ] = 0;
}

inline void tarjan (int x)
{
    dfn[x] = low[x] = ++Index;
    for (int i = Begin[x]; i + 1; i = Next[i])
    {
        int y = To[i];
        if (f[i]) continue;
        f[i] = f[i ^ 1] = 1;
        if (!dfn[y])
        {
            fa[y] = x;
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x])
                ++Ans, Vis[y] = 1;
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

inline void LCA (int x, int y)
{
    while (dfn[x] > dfn[y])
    {
        //cout<<x<<endl;
        if (Vis[x]) --Ans, Vis[x] = 0;
        x = fa[x];
    }

    while (dfn[y] > dfn[x])
    {
        //cout<<y<<endl;
        if (Vis[y]) --Ans, Vis[y] = 0;
        y = fa[y];
    }

    while (x != y)
    {
        if (Vis[x]) --Ans, Vis[x] = 0;
        if (Vis[y]) --Ans, Vis[y] = 0;
        x = fa[x], y = fa[y];
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("C.in", "r", stdin);
    freopen("C.out", "w", stdout);
#endif
    int cnt = 0;
    while (1)
    {
        e = 0;
        Index = 0;
        Ans = 0;
        memset(Begin, -1, sizeof(Begin));
        memset(dfn, 0, sizeof(dfn));
        memset(Vis, 0, sizeof(Vis));
        scanf("%d%d", &N, &M);
        if (!N && !M) break;
        for (int i = 1; i <= M; ++i)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            add_edge (x, y);
            add_edge (y, x);
        }

        tarjan(1);

        scanf("%d", &M);
        printf("Case %d:\n", ++cnt);
        while (M--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            LCA(x, y);
            printf("%d\n", Ans);
        }
        cout<<endl;
    }
    return 0;
}

hdu4587 TWO NODES

Description

n点的无向图，问删除两个点以后，该图最多被分成多少个联通快？

Solution

先枚举第一个点，然后跑一遍tarjan求出除去这个点之外的割点的数量，然后把去掉之后的联通块数量加那个值取max即可

Code

#include <bits/stdc++.h>

using namespace std;

const int Maxn = 5000 + 10;

int N, M;
int e, Begin[Maxn], To[Maxn * 2], Next[Maxn * 2], f[Maxn * 2];
int dfn[Maxn], low[Maxn], cut[Maxn], Index;
int root;

inline void Init ()
{
    e = 0;
    memset(Begin, -1, sizeof(Begin));
}

inline void init()
{
    memset(cut, 0, sizeof(cut));
    memset(dfn, 0, sizeof(dfn));
    memset(f, 0, sizeof(f));
    Index = 0;
}

inline void add_edge (int x, int y)
{
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    f[e++] = 0;
}

inline void tarjan (int x, int no)
{
    int son = 0;
    dfn[x] = low[x] = ++Index;
    for (int i = Begin[x]; i + 1; i = Next[i])
    {
        int y = To[i];
        if (y == no || f[i]) continue;
        f[i] = f[i ^ 1] = 1;
        if (!dfn[y])
        {
            ++son;
            tarjan(y, no);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x])
                cut[x] ++;
        }
        else low[x] = min(low[x], dfn[y]);
    }
    if (x == root) cut[x] --;
}

int main()
{
#ifdef hk_cnyali
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
#endif

    while (scanf("%d%d", &N, &M) != EOF)
    {
        Init();
        for (int i = 1; i <= M; ++i)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            ++x, ++y;
            add_edge (x, y);
            add_edge (y, x);
        }

        int Ans = 0;
        for (int i = 1; i <= N; ++i)
        {
            int Sum = 0;
            init();
            for (int j = 1; j <= N; ++j)
                if (i != j && !dfn[j])
                {
                    ++ Sum;
                    root = j;
                    tarjan(j, i);
                }
//          cout<<Sum<<endl;
            for (int j = 1; j <= N; ++j)
                if (i != j)
                    Ans = max(Ans, Sum + cut[j]);
        }
        cout<<Ans<<endl;
    }

    return 0;
}

hdu4612 Warm up

Description

给一个图， 求增加一条边之后的桥的数量最少是多少。有重边

Solution

先求桥的数量然后减去缩点求直径的长度即可

Code

//#pragma GCC optimize(2)
#include <bits/stdc++.h>

using namespace std;
//__attribute__((optimize("-O2")))

const int Maxn = 200000 + 100, Maxm = 2000000 + 100;

int N, M, Ans;
int e, Begin[Maxn], To[Maxm], Next[Maxm], f[Maxm];
int Q1[Maxm], Q2[Maxm];
int dfn[Maxn], low[Maxn], Index;
int vis[Maxn];
int belong[Maxn];
int c;
bitset <Maxn> Vis;

stack <int> S;

inline void Init()
{
    Ans = 0;
    c = 0;
    Index = e = 0;
    while (!S.empty()) S.pop();
    for (int i = 1; i <= N; ++i) Begin[i] = -1, belong[i] = dfn[i] = Vis[i] = low[i] = vis[i] = 0;
    memset(f, 0, sizeof(f));
    //memset(Vis, 0, sizeof(Vis));
    //Vis.clear();
}

inline void add_edge (int x, int y)
{
    To[e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    f[e ++] = 0;
}

inline void tarjan (int x)
{
    dfn[x] = low[x] = ++ Index;
    S.push(x);
    vis[x] = 1;
    int a, i;
    for (i = Begin[x]; i + 1; i = Next[i])
    {
        if (f[i]) continue;
        f[i] = f[i ^ 1] = 1;
        if (!dfn[To[i]])
        {
            tarjan(To[i]);
            low[x] = min(low[x], low[To[i]]);
            if (low[To[i]] > dfn[x])
                ++Ans;
        }
        else if (vis[To[i]]) low[x] = min(low[x], dfn[To[i]]);
    }
    if (low[x] == dfn[x])
    {
        ++c;
        while (1)
        {
            a = S.top(); S.pop();
            vis[a] = 0;
            belong[a] = c;
            if (a == x) break;
        }
    }
}

int pos, sum;

inline void dfs (int x, int dep)
{
    Vis[x] = 1;
    if (dep >= sum) pos = x, sum = dep;
    int y;
    for (int i = Begin[x]; i + 1; i = Next[i])
    {
        y = To[i];
        if (Vis[y]) continue;
        dfs (y, dep + 1);
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("E.in", "r", stdin);
    freopen("E.out", "w", stdout);
#endif
    int x, y, a;
    int i, j;
    while (1)
    {
        scanf("%d%d", &N, &M);
        if (!N && !M) break;
        Init();
        for (i = 1; i <= M; ++i)
        {
            scanf("%d%d", &x, &y);
            add_edge (x, y);
            add_edge (y, x);
        }

        for (i = 1; i <= N; ++i)
            if (!dfn[i])
                tarjan(i);
//      cout<<Ans<<endl;

        e = 0;
        for (i = 1; i <= N; ++i)
        {
            for (j = Begin[i]; j + 1; j = Next[j])
            {
                //              cout<<belong[i]<<" "<<belong[To[j]]<<endl;
                //add_edge1(belong[i], belong[To[j]]), add_edge1(belong[To[j]], belong[i]);
                if (belong[i] == belong[To[j]]) continue;
                Q1[++e] = belong[i], Q2[e] = belong[To[j]];
            }
        }

        memset(Begin, -1, sizeof(Begin));
        int cnt = e;
        e = 0;
        for (i = 1; i <= cnt; ++i)
            add_edge(Q1[i], Q2[i]), add_edge(Q2[i], Q1[i]);

        pos = sum = 0;
        dfs(1, 0);
        //memset(Vis, 0, sizeof(Vis));
        for (i = 1; i <= N; ++i) Vis[i] = 0;
        int now = pos;
        pos = sum = 0;
        dfs(now, 0);
        printf("%d\n", Ans - sum);
    }
    return 0;
}

hdu4694 Important Sisters

支配树模板

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 50000 + 10, Maxm = 100000 + 10;

int N, M;
int e, Begin[Maxn], To[Maxm * 2], Next[Maxm * 2];
int Index, dfn[Maxn], id[Maxn], fa[Maxn], f[Maxn], val[Maxn], idom[Maxn], semi[Maxn];
int Ans[Maxn];
vector <int> dom[Maxn], vec[Maxn];

inline void Init()
{
    e = Index = 0;
    for (int i = 1; i <= N; ++i) vec[i].clear(), dom[i].clear(), Begin[i] = dfn[i] = idom[i] = Ans[i] = 0, f[i] = val[i] = semi[i] = i;
}

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

inline void dfs (int x)
{
    dfn[x] = ++Index;
    id[Index] = x;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        vec[y].push_back(x);
        if (dfn[y]) continue;
        fa[y] = x;
        dfs(y);
    }
}

inline int find (int x)
{
    if (f[x] == x) return x;
    int y = find(f[x]);
    if (dfn[semi[val[f[x]]]] < dfn[semi[val[x]]]) val[x] = val[f[x]];
    return f[x] = y;
}

inline void Calc ()
{
    for (int i = 1; i <= Index; ++i)
    {
        int x = id[i];
        Ans[x] += x;
        if (idom[x]) Ans[x] += Ans[idom[x]];
    }
}

inline int mmin (int x, int y)
{
    return dfn[x] < dfn[y] ? x : y;
}

main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (~scanf("%lld%lld", &N, &M))
    {
        Init();
        for (int i = 1; i <= M; ++i)
        {
            int x, y;
            scanf("%lld%lld", &x, &y);
            add_edge (x, y);
        }

        dfs(N);

        for (int i = Index; i > 1; --i)
        {
            int x = id[i];
            for (int j = 0; j < vec[x].size(); ++j)
            {
                int now = vec[x][j];
                if (dfn[now] < dfn[x]) semi[x] = mmin(semi[x], now);
                else
                {
                    find(now);
                    semi[x] = mmin(semi[x], semi[val[now]]);
                }
            }

            f[x] = fa[x], dom[semi[x]].push_back(x);
            for (int j = 0; j < dom[fa[x]].size(); ++j)
            {
                int now = dom[fa[x]][j]; find(now);
                idom[now] = (dfn[semi[val[now]]] < dfn[semi[now]]) ? val[now] : fa[x];
            }
        }

        for (int i = 2; i <= Index; ++i)
        {
            int x = id[i];
            if (idom[x] != semi[x]) idom[x] = idom[idom[x]];
        }

        Calc();

        cout<<Ans[1];
        for (int i = 2; i <= N; ++i)
            cout<<" "<<Ans[i];
        cout<<endl;
    }
    return 0;
}