lessons/参考实现/02-强连通与双连通/POJ-1144.cpp

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

struct E { int to, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string line;
    while (cin >> n && n != 0) {
        getline(cin, line);
        vector<vector<E>> g(n);
        int edge_id = 0;
        while (getline(cin, line) && line != "0") {
            istringstream input(line);
            int u, v; input >> u; --u;
            while (input >> v) {
                --v;
                g[u].push_back({v, edge_id});
                g[v].push_back({u, edge_id});
                ++edge_id;
            }
        }
        vector<int> dfn(n), low(n);
        vector<bool> cut(n, false);
        int timer = 0;
        auto dfs = [&](auto &&self, int u, int parent_edge) -> void {
            dfn[u] = low[u] = ++timer;
            int children = 0;
            for (E e : g[u]) {
                if (e.id == parent_edge) continue;
                if (!dfn[e.to]) {
                    ++children; self(self, e.to, e.id);
                    low[u] = min(low[u], low[e.to]);
                    if (parent_edge != -1 && low[e.to] >= dfn[u]) cut[u] = true;
                } else low[u] = min(low[u], dfn[e.to]);
            }
            if (parent_edge == -1 && children >= 2) cut[u] = true;
        };
        for (int v = 0; v < n; ++v) if (!dfn[v]) dfs(dfs, v, -1);
        cout << count(cut.begin(), cut.end(), true) << '\n';
    }
}