lessons/参考实现/02-强连通与双连通/CodeForces-962F.cpp

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
struct E { int to, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<pair<int, int>> edges(m);
    vector<vector<E>> g(n);
    for (int id = 0; id < m; ++id) {
        int u, v; cin >> u >> v; --u; --v; edges[id] = {u, v};
        g[u].push_back({v, id}); g[v].push_back({u, id});
    }
    vector<int> dfn(n), low(n), edge_stack, seen(n, 0), answer;
    int timer = 0, stamp = 0;
    auto dfs = [&](auto &&self, int u, int parent_edge) -> void {
        dfn[u] = low[u] = ++timer;
        for (E e : g[u]) {
            if (e.id == parent_edge) continue;
            if (!dfn[e.to]) {
                edge_stack.push_back(e.id);
                self(self, e.to, e.id);
                low[u] = min(low[u], low[e.to]);
                if (low[e.to] >= dfn[u]) {
                    ++stamp;
                    vector<int> block;
                    int vertices = 0;
                    while (true) {
                        int id = edge_stack.back(); edge_stack.pop_back();
                        block.push_back(id);
                        auto [a, b] = edges[id];
                        if (seen[a] != stamp) seen[a] = stamp, ++vertices;
                        if (seen[b] != stamp) seen[b] = stamp, ++vertices;
                        if (id == e.id) break;
                    }
                    if (static_cast<int>(block.size()) == vertices) {
                        answer.insert(answer.end(), block.begin(), block.end());
                    }
                }
            } else if (dfn[e.to] < dfn[u]) {
                edge_stack.push_back(e.id);
                low[u] = min(low[u], dfn[e.to]);
            }
        }
    };
    for (int v = 0; v < n; ++v) if (!dfn[v]) dfs(dfs, v, -1);
    sort(answer.begin(), answer.end());
    cout << answer.size() << '\n';
    for (int id : answer) cout << id + 1 << ' ';
    cout << '\n';
}