{%hackmd @ioncamp/__style %}
# TIOJ 1879 . 我傳了一份code結果妳就來了
- BBC 裸題
- <font color="fart">WA 40</font> 可能原因
- 沒有考慮重邊

#include <bits/stdc++.h>
#define pii pair<int, int>
#define mk make_pair
#define pb push_back
using namespace std;

//BCC
const int maxn = 1e5 + 5;
int n, m;
int dep[maxn];
int t[maxn];
int low[maxn];
int bcc[maxn];
vector<vector<int>> bc;
int stamp = 1, bccID;
stack<int> stk;
vector<int> G[maxn];
vector<int> E;

void dfs(int u, int last_edge) {
    low[u] = t[u] = stamp++;
    stk.push(u);
    for (auto idx : G[u]) {
        int v = E[idx];
        if (t[v] == 0) {
            dfs(v, idx^1);
            low[u] = min(low[u], low[v]);
        }
        else if (idx!=last_edge){
            low[u] = min(low[u], t[v]);
        }
    }
    if (low[u] == t[u]) {
        int tmp;
        bccID++;
        bc.resize(bccID);
        do{
            tmp = stk.top();
            bcc[tmp] = bccID;
            bc[bccID - 1].pb(tmp);
            stk.pop();
        } while (tmp != u);
        sort(bc[bccID - 1].begin(), bc[bccID - 1].end());
    }
}

signed main() {
    cin >> n >> m;
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        G[u].pb(E.size());
        E.pb(v);
        G[v].pb(E.size());
        E.pb(u);
    }
    dfs(0, -1);
    sort(bc.begin(), bc.end());
    for (int i = 0; i < bc.size(); i++) {
        cout << i + 1 << ": ";
        for (int j : bc[i]) {
            cout << j << " ";
        }
        cout << "\n";
    }
}

###### tags: `題解`