图论的基础算法暂且不提，这里直接引出一种难度比较中等的算法 \(—— Tarjan\)
这是 \(Tarjan\) 研发出的算法，复杂度通常为 \(\Theta(n)\).
图论中的 \(Tarjan\) 可以解决图的连通性问题，比如割点割边等\(.\)
先提出一些定义 \(/\) 符号 \(:\)
- 连通块 ， 指一个任意两点互相可达的图
无向图的连通性
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\) 值为它本身，因为该点至少能回退到自己。
模板题 \(:\)
然后是一张丑陋的代码
#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;
}