洛谷 P8435. 【模板】点双连通分量
原题链接
中等
算法
(Tarjan) $O(N+M)$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
inline void chmin(int& x, int y) { if (x > y) x = y; }
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<vector<int>> to(n);
rep(i, m) {
int a, b;
cin >> a >> b;
if (a == b) continue;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
vector<int> ord(n, -1), low(n, -1);
int id = 0;
stack<int> stk;
vector<vector<int>> vcc;
function<void(int, int)> tarjan = [&](int v, int p) {
ord[v] = low[v] = id++;
stk.push(v);
if (!to[v].size()) {
vcc.emplace_back();
vcc.back().push_back(v);
return;
}
for (int u : to[v]) {
if (u == p) continue;
if (ord[u] != -1) chmin(low[v], ord[u]);
else {
tarjan(u, v);
chmin(low[v], low[u]);
if (low[u] >= ord[v]) {
vcc.emplace_back();
int nv;
do {
nv = stk.top(); stk.pop();
vcc.back().push_back(nv);
} while(nv != u);
vcc.back().push_back(v);
}
}
}
};
rep(v, n) {
if (ord[v] != -1) continue;
tarjan(v, -1);
}
cout << vcc.size() << '\n';
for (auto& comp : vcc) {
cout << comp.size() << ' ';
for (int v : comp) cout << v+1 << ' ';
cout << '\n';
}
return 0;
}