Finding articulation points
unknown
c_cpp
3 years ago
1.1 kB
6
Indexable
class ArticulationPoints { public: vector<int> tin, mn, cutVertices; vector<bool> used; int timer; ArticulationPoints(int MAXN){ timer = 0; used.resize(MAXN); mn.resize(MAXN); tin.resize(MAXN); } void dfs(int v, int par = -1) { used[v] = true; timer++; tin[v] = timer; mn[v] = tin[v]; int childNum = 0; bool isCutVertex = false; // Change the graph name to your own and create it for (int i = 0; i < (int) g[v].size(); i++) { int to = g[v][i]; if (!used[to]) { childNum++; dfs(to, v); if (par != -1 && mn[to] >= tin[v] && !isCutVertex) { isCutVertex = true; cutVertices.push_back(v); } mn[v] = min(mn[v], mn[to]); } else if (to != par) { mn[v] = min(mn[v], tin[to]); } } if (par == -1 && childNum > 1) cutVertices.push_back(v); } };
Editor is loading...