图论

图论的基础算法暂且不提，这里直接引出一种难度比较中等的算法 \(—— Tarjan\)

这是 \(Tarjan\) 研发出的算法，复杂度通常为 \(\Theta(n)\).

图论中的 \(Tarjan\) 可以解决图的连通性问题，比如割点割边等\(.\)

先提出一些定义 \(/\) 符号 \(:\)

1. 连通块 ， 指一个任意两点互相可达的图

无向图的连通性

1. Tarjan 割点

割点，可以简单地理解为可以满足

删去该点之后整张图的连通块数量会因而增加

的任意一个点

求割点可以简单的用 dfs树 来解决，这也是 tanjan 算法的原理。

可以记录两个数组 \(dfn[N],low[N]\) 来分别记录点在树上出现的时间戳，以及记录点可以不通过树边回溯到的树上深度最小的点。

我们记 \(T(u)\) 为以 \(u\) 为根的子树。引入两个定理。

定理 1.1

对于一颗 \(dfs\) 树，如果这棵树的根节点的子节点（子树）数量大于 1，那么这个点是一个割点。原因显然。

定理 1.2

对于 \(dfs\) 树上的点 \(u\) ，去讨论 \(u\) 下的子树的每一个节点，如果不存在 \(\forall v\in T(u)\) 满足 \(low[v]<u\) ，及没有任何一个点可以回溯到点 \(u\) 上面的点就可以判断 \(u\) 是一个割点 \(.\)

可以尝试感性地理解这个定理 \(:\)

如果子树上的任意一个点可以回退到 \(u\) 上面的点，也就代表这个点可以不用经过点 \(u\) 联通到其他连通块，这个时候点 \(u\) 并不是相当重要的，也就是可以删除点 \(u.\) 所以一个非根点可以成为割点当且仅当它对于它的子树至关重要。

联立两个定理，就可以用 \(O(n)\) 的复杂度求得，其中 \(low\) 可以在回溯的时候迭代。

注意，因为每一个点的遍历次数都仅为 \(1\)，所以无论这个图有多么毒瘤用这种方法求割点都是 \(\Theta(n)\) ， 原因显然。

常数也较为恒定，是一种比较简单的求割点方法，注意要保证图上的每一个点都被均匀地遍历到，否则在图不连通的情况下会吃大亏。

细节上来说，在每一个点刚刚遍历到的时候其 \(low\) 值为它本身，因为该点至少能回退到自己。

模板题 \(:\)

\(\color{black}{P3388}\)

然后是一张丑陋的代码

#include <bits/stdc++.h>
#define FOR(i,s,n) for(register int i=s;i<=n;++i)
#define ROF(i,n,s) for(register int i=n;i>=s;--i)
#define ll long long
using namespace std;
const int N=2e4+5;
int low[N],num[N],tot,root;
bool iscut[N];
vector<int> G[N];

void dfs(int u,int rt){
	low[u]=num[u]=++tot;
	int child = 0;
	for(auto v:G[u]){
		if(!num[v]){
			if(v!=rt)++child;
			dfs(v,u);
			low[u]=min(low[v],low[u]);
			if(low[v]>=num[u] && u!=root)iscut[u]=true;
		}
		else if(num[v]<num[u] && v!=rt)
			low[u]=min(low[u],num[v]);
	}
	if(u==root && child>=2) iscut[root]=true;
}

int main(){
	int ans=0,n,m;
	cin>>n>>m;
	int a,b;
	FOR(i,1,m){
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	FOR(i,1,n){
		root=i;
		dfs(i,i);
	}
	FOR(i,1,n){
		if(iscut[i])
			++ans;
	}
	cout<<ans<<endl;
	FOR(i,1,n){
		if(iscut[i])
			cout<<i<<' ';
	}
	return 0;
}