tarjan算法
原理：
我们考虑 DFS 搜索树与强连通分量之间的关系。
如果结点 是某个强连通分量在搜索树中遇到的第⼀个结点，那么这个强连通分量的其余结点肯定 是在搜索树中以 为根的⼦树中。 被称为这个强连通分量的根。
反证法：假设有个结点 在该强连通分量中但是不在以 为根的⼦树中，那么 到 的路径中肯 定有⼀条离开⼦树的边。但是这样的边只可能是横叉边或者反祖边，然⽽这两条边都要求指向的结点已 经被访问过了，这就和 是第⼀个访问的结点⽭盾了。得证。
思路：
在 Tarjan 算法中为每个结点 维护了以下⼏个变量：
1:dfn[u]深度优先搜索遍历时结点 的DFS序。
2:low[u]设以u为根的⼦树为Subtree[u]。low[u]定义为以下结点的dfn的最⼩值：
Subtree(u)中的结点；从 Subtree(u)通过⼀条不在搜索树上的边能到达的结点。
遍历时维护栈，⽤于求解强连通分量。 ⼀个结点的⼦树内结点的 dfn 都⼤于该结点的 dfn。 从根开始的⼀条路径上的 dfn 严格递增，low 严格⾮降。 按照深度优先搜索算法搜索的次序对图中所有的结点进⾏搜索。
在搜索过程中，对于结点u和与其v相邻的结点 考虑 3 种情况：
1. v未被访问：继续对v进⾏深度搜索。在回溯过程中，low[v]⽤low[u]更新 。因为存在从u到v的直接路径，所以v 能够回溯到的已经在栈中的结点,u也⼀定能够回溯到。
2. v被访问过，已经在栈中：即已经被访问过，根据low值的定义（能够回溯到的最早的已经在栈中 的结点），则⽤dfn[u]更新low[v] 。
3. v被访问过，已不在在栈中：说明v已搜索完毕，其所在连通分量已被处理，所以不⽤对其做操作。
代码实现：
void tarjan(int x){
dfn[x]=low[x]=++tim;//DFS序的赋值
sta[++top]=x;vis[x]=1;//入栈
sd[x]=x;//如果这个点不是强连通分量，缩点后它还是自己
for(int i=head[x];i;i=eg[i].nex){
int y=eg[i].to;
if(!dfn[y]){//v未被访问，继续对v进行深度搜索
tarjan(y);
low[x]=min(low[x],low[y]);//回溯，更新low[x]值
}
else{
if(vis[y]){//被访问过
low[x]=min(low[x],dfn[y]);//回溯，更新low[x]值
}
}
if(dfn[x]==low[x]){//找到一个强连通分量
int y;
while(y=sta[top--]){//依次出栈
sd[y]=x;//缩点
vis[y]=0;//出栈
if(x==y) break;
p[x]+=p[y];//点权集中
}
}
}
}
※：缩点后，整张图就变成了一个DAG,所以tarjan常常和拓扑排序一同使用。
例题就不插了，毕竟板子都还没过...
但！
还有一个问题！
目光聚焦到这几行代码：
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
///////////////////////////////////////////////////
else{
if(vis[y]){
low[x]=min(low[x],dfn[y]);
}
}
为什么一个括号里是low[y],一个是dfn[y]?
在这里，其实都写low[y]也是正确的，但是在割点割边的时候便是有问题的了。
原因：未出现的邻居，可能会连到之前出现过的点，所以是LOW[]；已经出现的邻居再次出现，就必然是强连通分量图中的一个点，可能是最小时序最小根，取它的DFN，继续计算LOW
割点
定义：
对于⼀个⽆向图，如果把⼀个点删除后这个图的极⼤连通分量数增加了，那么这个点就是这个图 的割点（⼜称割顶）。
通俗理解，如果去掉割点能将这个图割成更多小块，这个点就是割点
原理&实现：
⾸先，我们按照 DFS 序给他打上时间戳（访问的顺序）。
这些信息被我们保存在⼀个叫做 dfn 的数组中。 还需要另外⼀个数组 low ，⽤它来存储不经过其⽗亲能到达的最⼩的时间戳。 例如 low[2] 的话是 1， low[5] 和 low[6] 是 3。 然后我们开始 DFS，我们判断某个点是否是割点的根据是：对于某个顶点 ，如果存在⾄少⼀个顶 点 （ 的⼉⼦），使得low[v]>=dfs[u] ，即不能回到祖先，那么u点为割点。 另外，如果搜到了⾃⼰（在环中），如果他有两个及以上的⼉⼦，那么他⼀定是割点了，如果只有 ⼀个⼉⼦，那么把它删掉，不会有任何的影响。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m;
int idx=0;
int tim;
int root;
struct node {//邻接表建图
int to;
int from;
int nex;
} eg[N]; int head[N];
int low[N],dfn[N];
int vis[N];
int cnt[N]; void add(int x,int y) {//建图
eg[++idx].from=x;
eg[idx].to=y;
eg[idx].nex=head[x];
head[x]=idx;
} void tarjan(int x) {
low[x]=dfn[x]=++tim;
vis[x]=1;
int flag=0;
for(int i=head[x];i;i=eg[i].nex){
int y=eg[i].to;
if(!vis[y]) {
tarjan(y);
low[x]=min(low[y],low[x]);
if(low[y]>=dfn[x]) {//回不到更早的祖先节点
flag++;//统计儿子数
if(x!=root||flag>1) {//如果是根节点，要有2个儿子回不到祖先
cnt[x]=1;//标记割点
}
}
}
else low[x]=min(low[x],dfn[y]);//如果y已经被遍历，则low[x]直接更新
}
} int main() {
cin>>n>>m;
for(int i=1; i<=m; i++) {
int x,y;
cin>>x>>y;
add(x,y);
add(y,x);//建图
}
for(int i=1; i<=n; i++) {
if(!vis[i]) {
root=i;
tarjan(root);
}
}
int ans=0;
for(int i=1; i<=n; i++) {
ans+=cnt[i];
}
cout<<ans<<endl;
for(int i=1;i<=n;i++) {
if(cnt[i]) cout<<i<<" ";
}
return 0;
}
割边
定义：
对于⼀个⽆向图，如果删掉⼀条边后图中的连通分量数增加了，则称这条边为桥或者割边。严谨 来说，就是：假设有连通图 G=V,E， 是其中⼀条边（即 e∈E），如果 G-e是不连通 的，则边 e是图 G的⼀条割边（桥）。
通俗来讲，如果去掉边能将这个图割成更多小块，这条边就是割边（桥）
实现：
实现 和割点差不多，只要改⼀处： low[v]>dfn[u]就可以了，⽽且不需要考虑根节点的问题。 原来我们求割点的时候，发现点 v不经过⽗节点 u就⽆法回到祖先节点，所以顶点u 是割点。
对于边来说，如果⼦节点 只能通过当前这条边到达⽗亲节点 ，则说明当前这条边是割边。但是要 注意的是，我们只改上⾯说的那⼀处，会有问题。我们⽤两条边来表示⽆向图的⼀条边，在搜索 的时 候会通过反边往⽗亲 ⾛，如果这个时候更新 的话，将会导致错误。所以需要特判反边（注意，如 果⽤特判⽗亲节点的⽅法规避反边，会在重边图出错）。
代码就懒得打了（其实是不会）