Finding articulation points
unknown
c_cpp
4 years ago
1.1 kB
7
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...