夏晓光(loveJY)的博客

From 2020省选复习

首先我们小手一挥分出类

1. 强联通分量
2. 割点
3. 割边
4. 点双连通分量
5. 边双连通分量

目前完成了123,如果考45我也大概率不会....

算法一

我们用low数组表示最多经过一条返祖边到达的最小编号是什么,dfn表示这个点的编号是什么

然后dfs经过的入栈,当low==dfn的时候,说明一些点能构成一个强联通分量了,因为我们已经不能再回去了

否则就还可以再缩扩大连通块大小

算法二

首先我们要知道的是我们访问的点能作为割点,说明存在一个儿子,low值大于等于这个点dfn值

但是这个东西在根的时候是伪的,因为根的值一定是最小的....所以根要单独看,是当存在多于一个儿子时就是割点啦

算法三

把算法二的low>=dfn改改,改为low>dfn

相当于去掉这个边,子树就再不能走回u了

code1:

int dfn[MAXN],low[MAXN],fl[MAXN],st[MAXN],tp,bel[MAXN],T,dep;
inline void tarjan(int u) {
	low[u]=dfn[u]=++dep;
	fl[u]=1;
	st[++tp]=u;
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u]=std::min(low[u],low[v]);
		} else if(!fl[v])continue;
		low[u]=std::min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]) {
		++T;
		while(1) {
			int v=st[tp];
			bel[v]=T;
            fl[v]=0;
			tp--;
			if(v==u)break;
		}

	}
	return ;
}

至于fl去掉横跨边有没有用....不知道

code2:

inline void tarjan(int u)
{
	dfn[u]=low[u]=++dep;
	int tmp=0;
	for(int i=home[u]; i ; i=nxt[i]) {
		int v=to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[v],low[u]);
			if(u==rt) {
				++tmp;
			}
			if(low[v]>=dfn[u] && u!=rt) {
				ap[++tot]=u;
			}
		}
		low[u]=min(low[u],dfn[v]);
	}
	if(u==rt&&tmp>1) {
		ap[++tot]=u;
	}
}