오랜만에 unordered_set 쓰는 특이한 문제였음.
핵심은 그리디하게 지워도 상관 없다는 점


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57#include <iostream> #include <algorithm> #include <unordered_set> constexpr int MAXN = 200'004; constexpr int MAXQ = (1 << 18); int N, M; std::unordered_set<int> E[MAXN]; int Q[MAXQ], qf, qr; void clear() { for (int i = 0; i <= N; ++i) E[i].clear(); } int main() { using namespace std; ios::sync_with_stdio(false); cin.tie(nullptr); int tc; cin >> tc; for (int t = 1; t <= tc; ++t) { cin >> N >> M; clear(); for (int i = 0; i < M; ++i) { int x, y; cin >> x >> y; E[x].insert(y); E[y].insert(x); } qf = qr = 0; for (int i = 1; i <= N; ++i) { if (E[i].size() == 2) Q[qr++] = i; } int rm = 0; while (qf < qr) { const int np = Q[qf++]; if (E[np].size() != 2) continue; auto it = E[np].begin(); const int e1 = *it; const int e2 = *(++it); if (E[e1].find(e2) != E[e1].end()) { ++rm; E[e1].erase(np); E[e2].erase(np); if (E[e1].size() == 2) Q[qr++] = e1; if (E[e2].size() == 2) Q[qr++] = e2; } } cout << "Case #" << t << '\n' << (N - rm) << '\n'; } }