点双连通分量（Tarjan）

题目概述

对于一个 个节点 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。

算法主要步骤

1. 维护一个栈
2. 第一次访问某一个点时，将其入栈
3. 当割点判断的法则成立时，即时，不断从栈中弹出节点，直到被弹出，这些被弹出的点和一起构成一个点双连通分量

思考

1. 对于一个点双，它在 搜索树中 值最小的点一定是割点或者树根。
2. 当这个点是割点时，它所属的点双必定不可以向它的父亲方向覆盖更多点，因为一旦覆盖了，它就成为了新的子图的一个割点，不是点双。所以它应该归到其中一个或多个子树里的点双中。
3. 当这个点是树根时，它的 值是整棵树里最小的。它若有两个以上子树，那么它是一个割点；它若只有一个子树，它一定属于它的直系儿子的点双，因此包括它, 它若是一个独立点，视作一个单独的点双。

代码

#include <bits/stdc++.h>
// 如果是自环就不加边
const int maxn = 5e5 + 5;
const int inf = 4e6 + 10;
int cnt = 0, ccnt = 0, root = 0;
int head[maxn], low[maxn], dfn[maxn];
int col[maxn]; // 属于哪个点双
int num = 0; // 点双记数
bool vis[maxn] = {0}; // 在不在栈中4
//bool ifcut[maxn] = {0}; // 是否是割点
std::vector<int> g[maxn];
std::stack<int> stk;
struct Edge
{
    int s, t, next;
}edge[inf];

void AddEdge(int s, int t)
{
    edge[++cnt].s = s;
    edge[cnt].t = t;
    edge[cnt].next = head[s];
    head[s] = cnt;
}

void tarjan(int x)
{
    low[x] = dfn[x] = ++ccnt;
    vis[x] = 1;
    stk.push(x);
    if (x == root && head[x] == -1)
    {
        num++;
        g[num].push_back(x);
        return;
    }
    //int son = 0;
    for (int i = head[x]; i != -1; i = edge[i].next)
    {
        int y = edge[i].t;
        if (dfn[y] == 0)
        {
            tarjan(y);
            low[x] = std::min(low[x], low[y]);
            if (dfn[x] <= low[y])
            {
                num++;
                // if (x != root || son > 1)
                // {
                //     num += (!ifcut[x]);
                //     ifcut[x] = 1;
                //     while(true)
                //     {
                //         int top = stk.top();
                //         g[num].push_back(top);
                //         stk.pop();
                //         if (top == y) 
                //         {
                //             g[num].push_back(x);
                //             break;
                //         }
                //     }
                // }
                // 注意这里树根不用再像割点一样特判了，因为不管它是不是割点，都可以加入到点双中
                // 一个割点可以属于不同的点双，所以这里num要++
                while(true)
                {
                    int top = stk.top();
                    g[num].push_back(top);
                    stk.pop();
                    if (top == y) 
                    {
                        break;
                    }
                }
                g[num].push_back(x);
            }
        }
        else
        {
            low[x] = std::min(low[x], dfn[y]);
        }
    }
}

int n = 0, m = 0, u = 0, v = 0;
int main()
{
    std::cin >> n >> m;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++)
    {
        std::cin >> u >> v;
        if (u == v) continue;
        AddEdge(u, v);
        AddEdge(v, u);
    }

    for (int i = 1; i <= n; i++)
    {
        if (dfn[i] == 0)
        {
            root = i;
            tarjan(i);
        }
    }
    std::cout << num << '\n';
    for (int i = 1; i <= num; i++)
    {
        std::cout << g[i].size() << " ";
        for (int x : g[i])
        {
            std::cout << x << " ";
        }
        std::cout << '\n';
    }
    return 0;
}