割边、边双连通分量和缩点

const int N = 200005, M = 1000005; // M 开至无向边数的 2 倍以上

int head[N], to[M], nxt[M], cnt = 2;
int dfn[N], low[N], tot;
int stk[N], top;
int bel[N], ebcc_cnt;
bool is_bridge[M >> 1];

vector<int> tree[N];

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

void tarjan(int u, int in_edge) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    for (int i = head[u]; i; i = nxt[i]) {
        if (i == (in_edge ^ 1)) continue;
        int v = to[i];
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {
        if (in_edge) is_bridge[in_edge >> 1] = true; // 非树根则上方边必为割边
        ++ebcc_cnt;
        do {
            bel[stk[top]] = ebcc_cnt;
        } while (stk[top--] != u);
    }
}

void build_tree(int n) {
    for (int u = 1; u <= n; ++u)
        for (int i = head[u]; i; i = nxt[i])
            if (bel[u] != bel[to[i]])
                tree[bel[u]].push_back(bel[to[i]]);
}