连通分量专题

图上问题->树上问题->序列问题

连通分量专题

强连通分量(SCC)
对于一个有向图，当其中任意两点都能互相到达时，我们认为这是强联通的

int dfn[N],low[N],belong[N],cnt,tot;
bool instack[N];
vector<int>scc[N];
stack<int>st;
void dfs(int u){
	dfn[u]=low[u]=++cnt;
	st.push(u);instack[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
		}else if(instack[v])low[u]=min(low[u],low[v]);
		//v has gone to u,u can also to v
	}
	if(low[u]==dfn[u]){
		++tot;
		while(st.top()!=u){
			belong[st.top()]=tot;
			instack[st.top()]=0;
			scc[tot].push_back(st.top());
			st.pop();
		}
		belong[u]=tot;
		scc[tot].push_back(st.top());
		instack[u]=0;
		st.pop();
	}
}

双联通分量
双联通分量仅存在于无向图

在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个，且不能删 u 和 v 自己）都不能使它们不连通，我们就说 u 和 v 点双连通。

边双
边双连通具有传递性
在无向图中，对于任意两个点 u 和 v，如果无论删去哪条边都不能使它们不连通，我们说该图边双联通。

点双
点双连通不具有传递性
在无向图中，对于任意两个点 u 和 v，如果无论删去哪个点都不能使它们不连通，我们说该图点双联通。

割点
对于一点u，若删掉u，连通块数量增加1，则该点为割点

割边
对于一条边e，若删掉e，连通块数量增加1，则该点为割边