割点、强连通分量

算是之前的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;
	}
}

(因为两个板子写的时间相距较长,码风差距较大,凑合着看吧。。。)

上一篇:每天进步一点点之树的遍历


下一篇:STM32+USART+蓝牙模块(BT04)