前置知识

• 图论相关概念
• 割点和桥
• 强连通分量

点双连通分量

在一个无向图中，若删除图中的任意一个点，这个图还能连通，则称这个图为点双连通

例题：P8435 【模板】点双连通分量

在书写代码的时候有需要注意的地方会在程序中标注。

#include <bits/stdc++.h> 
using namespace std;
const int maxn = 5e5 + 5;

int n, m;
vector<int> G[maxn], ans[maxn];
int dfn[maxn], low[maxn], cnt;
int top, stk[2000005];

void dfs(int x, int fa) {
    dfn[x] = low[x] = ++dfn[0];
    stk[++top] = x;
    int son = 0;
    for(auto to : G[x]) {
        if(!dfn[to]) {
            if(to == fa) continue;
            son++;
            dfs(to, x);
            low[x] = min(low[x], low[to]);                                  //注意dfn和low数组有没有搞混 
            if(low[to] >= dfn[x]) {                      
                cnt++;
                int tmp = 0;
                while(stk[top + 1] != to) ans[cnt].push_back(stk[top--]);
                ans[cnt].push_back(x);
            }
            
        }
        else if(to != fa)low[x] = min(low[x],dfn[to]);
    }
    if(son == 0 && fa == 0) ans[++cnt].push_back(x);                        //不要忘记判读顶点 
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//  freopen("AKIOI.in", "r", stdin);
//  freopen("AKIOI.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) {
        if(dfn[i] != 0) continue;
        top = 0;                    //不要忘记清空栈 
        dfs(i, 0);
    }
    cout << cnt << '\n';
    for(int i = 1; i <= cnt; i++) {
        cout << ans[i].size() << " ";
        for(auto j : ans[i]) cout << j << " ";
        cout << "\n";
    }
    return 0;
    
}

边双连通分量

在一个无向图中，若删除图中的任意一条边，这个图还能连通，则称这个图为点双连通

例题：P8436 【模板】边双连通分量

在书写代码的时候有需要注意的地方会在程序中标注。

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int maxn = 5e5 + 5;

int n, m, cnt = 0;
vector<pair<int, int> > G[maxn];
vector<int> ans[maxn];
int dfn[maxn], low[maxn];
stack<int> stk;

void tarjan(int x, int fa) {
    low[x] = dfn[x] = ++dfn[0];
        stk.push(x);
    for(auto i : G[x]) {
        int to = i.first, it = i.second;    
        if (it == (fa ^ 1)) continue;           //利用位运算判断重边 
        if(!dfn[to]) {
            tarjan(to, it);
            low[x] = min(low[x], low[to]);      //dfn和low不要搞错 
        }
        else low[x] = min(low[x], dfn[to]);
    }
    if(dfn[x] == low[x]) {
        cnt++;
        ans[cnt].push_back(x);
        while(!stk.empty() && stk.top() != x) {ans[cnt].push_back(stk.top()), stk.pop();}   //出栈的操作需要注意 
        stk.pop();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("AKIOI.in", "r", stdin);
    // freopen("AKIOI.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        G[u].push_back(make_pair(v, i * 2));        //给每条边编号方便去重 
        G[v].push_back(make_pair(u, i * 2 + 1));
    }
    for(int i = 1; i <= n; i++) {
        if(!dfn[i]) tarjan(i, 0);
    }
    cout << cnt << "\n";
    for(int i = 1; i <= cnt; i++) {
        cout << ans[i].size() << " ";
        for(auto j : ans[i]) cout << j << " ";
        cout << "\n";
    }

    return 0;
}