双连通分量
割边：无向图中，删除这条边会使图不连通的边（又叫桥）。
割点：无向图中，删除这个点会使图不连通的点。
边双连通：两点 \(u,v\) 间不存在割边，就称 \(u,v\) 边双连通。即：删去 \(u,v\) 间任意一边，\(u,v\) 仍然连通。
点双连通：两点 \(u,v\) 间不存在割点，就称 \(u,v\) 点双连通。即：删去 \(u,v\) 间任意一点，\(u,v\) 仍然连通。
边双连通分量（eDCC）：无向图中的极大边双连通子图。
点双连通分量（vDCC）：无向图中的极大点双连通子图。
Tarjan
无向图割边割点、双连通分量均可以使用 Tarjan 算法高效求解。
求割边
对于一条边 \((u,v)\)，若 \(v\) 无法回溯到 \(u\) 及以前搜到的节点，则若删去 \((u,v)\)，\(u\) 与 \(v\) 就无法连通，因此 \((u,v)\) 是一条割边。
在 Tarjan 算法中，注意更新 \(low_u\) 时跳过反向边，然后判断 \(low_v>dfn_u\) 即可。
void tarjan(int u,int fa){low[u]=dfn[u]=++dfncnt;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(!dfn[v]){tarjan(v,i);if(low[v]>dfn[u]) ans[++idx].from=u,ans[idx].to=v;low[u]=min(low[u],low[v]);}else if((i^1)!=fa){//判断反向边。需要链式前向星 tot 从 2 开始low[u]=min(low[u],dfn[v]);}}return ;
}
求割点
同理，对于一点 \(u\)，若其一子节点 \(v\) 不能回溯到 \(u\) 之前搜到的节点，则 \(u\) 是个割点。只需要把 \(low_v>dfn_u\) 改为 \(low_v\ge dfn_u\) 即可。
特例是 DFS 树的根节点，如果在 DFS 树上根只有一个儿子，那么删除根剩下的节点依然连通。当儿子数 \(\ge2\) 时，根才是割点。
但要注意 \(u\) 可能不止一个子节点满足以上条件，会多次算出 \(u\)。
void tarjan(int u,int fa){low[u]=dfn[u]=++dfncnt;int cnt=0;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(!dfn[v]){tarjan(v,i);if(low[v]>=dfn[u]&&fa!=-1) vis[u]=1;low[u]=min(low[u],low[v]);cnt++;}else if((i^1)!=fa){//判断反向边。需要链式前向星 tot 从 2 开始low[u]=min(low[u],dfn[v]);}}if(fa==-1&&cnt>1) vis[u]=1;return ;
}
求 eDCC
对于一个无向图，由于我们已确定搜索开始的点，整张图的 DFS 搜索树就已经确定下来。此时删掉所有 DFS 搜索树上边的反向边，构造出一个有向图。显然，有向图的 SCC 等价于无向图的 eDCC。
并且，由于无向边相邻两点互相可达，图上便不存在（对于 DFS 树的）横叉边，因为两点若有边相连，两点均可成为对方的祖先，所以搜索时总是会先构成祖先关系。所以只存在返祖边，自然不用判断走到的已访问的点是否在栈中。
int dfn[N],low[N],dfncnt,st[N],top;
int dcc[N],dc;//结点 i 所在 eDCC 的编号，eDCC 计数
int sz[N];//eDCC i 的大小
void tarjan(int u,int fa) {low[u]=dfn[u]=++dfncnt,st[++top]=u;for(int i=h[u];i;i=e[i].nxt) {int v=e[i].to;if(!dfn[v]){tarjan(v,i);low[u]=min(low[u],low[v]);}else if((i^1)!=fa){//判断反向边。需要链式前向星 tot 从 2 开始low[u]=min(low[u],dfn[v]);}}if(dfn[u]==low[u]) {dc++;while(st[top]!=u) {dcc[st[top]]=dc;sz[dc]++;top--;}dcc[st[top]]=dc;sz[dc]++;top--;}
}