DFS 桥与割点 tarjan 算法

强连通分量：有向图中的极大强连通子图称作有向图的强连通分量.
极大强连通子图：把图的所有结点用最少的边将其连接起来的子图.
一个顶点也是极大强连通子图

任何一个强连通分量，必定是对原图的深度优先搜索树的子树。
只要确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量即可

https://www.luogu.com.cn/problem/P2863#sub
#include
#include
#include

const int MAXN = 50000 + 2;
int n, m, head[MAXN], cnt;
int low[MAXN], dfn[MAXN], num;
int res = 0;
bool inSt[MAXN];
struct Edge
{
    int to;
    int next;
}edges[MAXN];

void add(int u, int v)
{
    edges[++cnt].next = head[u];
    edges[cnt].to = v;
    head[u] = cnt;
}

//  求强连通分量
void tarjan2(int u, std::stack& st)   
{
    dfn[u] = low[u] = ++num;
    st.push(u);
    inSt[u] = true;
    for (int i = head[u]; i > 0; i = edges[i].next)
    {
        int v = edges[i].to;
        if (!dfn[v]) // v is unvisited
        {
            tarjan2(v, st);
            // backtracking update
            low[u] = low[u] > low[v] ? low[v] : low[u];
        }
        else if (inSt[v])//能通过非父子边找到最小祖先 
        {
            low[u] = low[u] > dfn[v] ? dfn[v] : low[u];
        }
    }

    if (low[u] == dfn[u])
    {
        int t = u;
        int tol = 0;
        do {
            t = st.top();
            st.pop();
            inSt[t] = false;
            ++tol;
        } while (u != t);

        if (tol > 1)
            ++res;
    }
}

void init()
{
    memset(head, 0, sizeof(head));
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    cnt = num = 0;
}

int main()
{
    std::stack ans;

    std::cin >> n >> m;
    init();
    int u, v;
    while (m--)
    {
        std::cin >> u >> v;
        add(u, v);
    }

    for (int i = 1; i <= n; ++i)  //for unconnected graph, needs to loop every vertex
    {
        if (!dfn[i])
        {
            tarjan2(i, ans);
        }
    }

    std::cout << res << std::endl;

    return 0;
}
 

如果去掉无向连通图G中的一条边e, 图G分裂为两个不相连的子图，那么e为图G的桥或者割边。
如果去掉无向连通图G中的一个点v及v关联的所有边，
图G分裂为两个或者两个以上不相连的子图，那么v为图G的割点。
时间戳： dfn[u]表示结点u的深度优先遍历序号
追溯点: low[u]表示结点u或者u的子孙能通过非父子边找到的dfn最小值，即通过非父子边找到最小祖先。

tarjan算法
初始时, low[u]=dfn[u], 
如果该结点的邻接点未被访问，则一直进行深度优先遍历，
回溯更新路径上所有祖先结点的low值 low[u]=min(low[u], low[v]);
如果某个结点能通过非父子边找到最小祖先， 则low[u]=min(low[u], dfn[v])

桥的判定法则： 无向边(u,v)是桥，当且仅当在搜索树上存在u的一个子节点v时，满足low[v]>dfn[u]，
即孩子的low值大于自己的dfn值。

割点的判定法则： 若u不是根结点，则u是割点，当且仅当在搜索树上存在u的一个子结点v, 满足low[v]>=dfn[u];
若u是根结点，则u是割点，当且仅当在搜索树上至少存在两个子结点，并满足low[v]>=dfn[u]。

#include

const int MAXN = 1000 + 2;
int n, m, head[MAXN], cnt, root;
int low[MAXN], dfn[MAXN], num;

struct Edge
{
    int to;
    int next;
}edges[MAXN];

void add(int u, int v)
{
    edges[++cnt].next = head[u];
    edges[cnt].to = v;
    head[u] = cnt;
}

// 求桥
void tarjan_bridge(int u, int fa)   // fa is u's parent
{
    dfn[u] = low[u] = ++num;
    for (int i = head[u]; i > 0; i = edges[i].next)
    {
        int v = edges[i].to;
        if (v == fa) // v is u's father
            continue;
        if (!dfn[v]) // v is unvisited
        {
            tarjan_bridge(v, u);
            // backtracking update
            low[u] = low[u] > low[v] ? low[v] : low[u];
            if (low[v] > dfn[u])
                std::cout << u << " --> " << v << " is one bridge edge" << std::endl;
        }
        else
            low[u] = low[u] > dfn[v] ? dfn[v] : low[u];
    }
}

// 求割点
void tarjan_artpoint(int u, int fa)   // fa is u's parent
{
    dfn[u] = low[u] = ++num;
    int children = 0;
    for (int i = head[u]; i > 0; i = edges[i].next)
    {
        int v = edges[i].to;
        if (v == fa) // v is u's father
            continue;
        if (!dfn[v]) // v is unvisited
        {
            tarjan_artpoint(v, u);
            // backtracking update
            low[u] = low[u] > low[v] ? low[v] : low[u];
            if (low[v] >= dfn[u])
            {
                ++children;
                if (u != root || children > 1)
                    std::cout << u << " is articulation point" << std::endl;
            }
        }
        else
            low[u] = low[u] > dfn[v] ? dfn[v] : low[u];
    }
}

void init()
{
    memset(head, 0, sizeof(head));
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    cnt = num = 0;
}

int main()
{
    // 输入结点数，边数
    while (std::cin >> n >> m)
    {
        init();
        int u, v;
        while (m--)
        {
            std::cin >> u >> v;
            add(u, v);
            add(v, u);
        }

        for (int i = 1; i <= n; ++i)  //for unconnected graph, needs to loop every vertex
        {
            if (!dfn[i])
            {
                root = i;
                //tarjan_bridge(i, 0);
                tarjan_artpoint(i, 0);
            }
        }
    }

    return 0;
}

5 5
1 2
1 3
3 4
3 5
4 5
1 --> 3 is one bridge edge
1 --> 2 is one bridge edge

5 5
1 2
1 3
3 4
3 5
4 5
3 is articulation point
1 is articulation point