算是之前的DFS树的一个具体应用,写个模板。
割点:
void DFS(int u) {
dfn[u] = low[u] = ++ind;
int childnum = 0;
if(u == root) childnum = -1;
for(int i = first[u]; i; i = e[i].next) {
int v = e[i].to;
if(!dfn[v]) {
DFS(v), low[u] = min(low[u], low[v]);
if(low[v] == dfn[u]) ++childnum;
}
else low[u] = min(low[u], dfn[v]);
}
if(childnum >= 1) p[++cnt] = u;
}
强连通分量:
void DFS(int u) {
dfn[u] = low[u] = ++ind;
sta[++top] = u, insta[u] = 1;
for(auto v : to[u]) {
if(!dfn[v]) DFS(v), low[u] = std::min(low[u], low[v]);
else if(insta[v]) low[u] = std::min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++cnt;
while(sta[top] != u){
scc[sta[top]] = cnt;
insta[sta[top--]] = 0;
}
scc[sta[top]] = cnt;
insta[sta[top--]] = 0;
}
}
(因为两个板子写的时间相距较长,码风差距较大,凑合着看吧。。。)