CSES - Shared codeLink to this code:
https://cses.fi/paste/3eb705518307169f935586/
// Fixed https://codeforces.com/blog/entry/68138#comment-650743
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 300005;
int bridgec;
vector<int> adj [MAX_N];
int lvl [MAX_N];
int dp [MAX_N];
vector<int> ans;
void visit (int vertex) {
dp[vertex] = 0;
vector<int> temp;
int par = 0;
int child = 0;
for (int nxt : adj[vertex])
{
if (lvl[nxt] == 0)
{ /* edge to child */
child++;
if (!temp.empty())
{
temp[temp.size() - 1] -= par;
par = 0;
}
lvl[nxt] = lvl[vertex] + 1;
visit(nxt);
dp[vertex] += dp[nxt];
temp.push_back(dp[nxt]);
}
else if (lvl[nxt] < lvl[vertex])
{ /* edge upwards */
dp[vertex]++;
}
else if (lvl[nxt] > lvl[vertex])
{ /* edge downwards */
dp[vertex]--;
par++;
}
}
/* the parent edge isn't a back-edge, subtract 1 to compensate */
dp[vertex]--;
//Special Cases
if (child == 0)
return;//leave node
if (vertex == 1)
{
// root node
if (child > 1)
{
// cout << "vertex " << vertex << endl;
ans.push_back(vertex);
bridgec++;
}
return;
}
//General Cases
temp[temp.size() - 1] -= par;
int flag = 0;
for (int x : temp)
{
if (x > 0) continue;
else {
flag = 1;
}
}
if (flag)
{
// cout << "vertex " << vertex << endl;
ans.push_back(vertex);
bridgec++;
}
}
int main () {
/* problem statement: given a connected graph. calculate the number of articulation points. */
ios_base::sync_with_stdio(0); cin.tie(0);
int vertexc, edgec;
cin >> vertexc >> edgec;
for (int i = 0; i < edgec; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
lvl[1] = 1;
visit(1);
// cout << bridgec << endl;
cout << ans.size() << '\n';
for (auto v : ans) cout << v << ' ';
}