题面：
给你一个 n 个点，m* 条边的无向图简单图。求割点数量，割边数量，极大点双连通分量数量，极大点双连通分量包含边数的最大值。
割点：在图中移除这个点后，存在一个点对在原图中连通在新图中不连通。
割边：在图中移除这条边后，存在一个点对在原图中连通在新图中不连通。
点双连通分量：原图的一个点数大于 1 的连通子图，不存在对于这个子图的割点。
极大点双连通分量：是点双连通分量，且任意新增一个点后不是点双连通分量。
Tarjan主要基于dfs的思想，用来求解图的连通性问题。算法思想：
- 时间戳：记录在dfs时每个截点被访问的顺序，用dfn[x]来表示。
- 搜索树：从某个节点出发进行dfs，访问到的边和节点构成的树。
- 追溯值：用low[x]表示，表示满足下列条件的节点中dfn的最小值：
- x为根的搜索树中的所有节点
- 通过一条不在搜索树上的边，能到达搜索树的节点
这样追溯值就表示x点属于包含low[x]节点的环（如果有环的话）。
追溯值的计算方法（dfs回溯的时候算）：
先让$$low[x] = dfn[x]$$，然后对x的每条边能到达的点y：
- 若y在x搜索树上（y>x)，则$$low[x] = min(low[x],low[y])$$
- 若y不在x的搜索树上（y<x），则$$low[x] = min(low[x],dfn[y])$$
桥
边(x,y)为桥当且仅当$$dfn[x]<low[y]$$
如果$$low[y]<=dfn[x]$$，说明有另一条路可以连回x以上，说明该边不是桥。
割点
点x是割点当且仅当$$dfn[x]<=low[y]$$
就算回路连回x点，删掉x点还是能把图拆断
参考代码：
void tarjan(int x){
dfn[x]=low[x]=++num;
int flag=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=flag||flag>1){
cur[x]=1;
}
}
}
else low[x]=min(low[x],dfn[y]);
}
}
边双连通分量
定义：没有割边的分量
去掉桥后dfs即可
点双连通分量（vDCC）
在tarjan过程中维护一个栈:
当第一次访问一个节点时，将其入栈；当$$dfn[x]<=low[y]$$成立时（找到割点），一直弹栈直至y被弹出，x->y构成一个vDCC
参考代码：
void tarjan_dcc(int x){
dfn[x]=low[x]=++num;
stac[++top]=x;
if(x==root&&head[x]==0){
//孤立点
dcc[++cnt].push_back(x);
return ;
}
int flag=0;
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(!dfn[y]){
tarjan_dcc(y);
low[x]=minn(low[x],low[y]);
if(low[y]>=dfn[x]){
flag++;
if(x!=root||flag>1)cur[x]=1;
cnt++;
int z;
do{
z=stac[top--];
dcc[cnt].push_back(z);
}while(z!=y);
dcc[cnt].push_back(x);
}
}
else low[x]=minn(low[x],dfn[y]);
}
}
强连通分量
注意点双是无向图的概念，强连通分量是有向图的概念。
与求点双的方法类似，但是强连通要求$$dfn[x]==low[y]$$时才能开始退栈。
参考
[tarjan算法(新) | Liyue (theshineyue.github.io)](https://theshineyue.github.io/2021/10/30/Tarjan 算法总结/)