一、Tarjan 求割边
桥（割边）：无向连通图中，去掉一条边，图中的连通分量数增加，则这条边，称为 桥 或 割边。
判断桥：一条无向边 (x,y) 是桥，当且仅当搜索树上存在 x 的一个子节点 y，满足：dfn[x]<low[y]。（根据定义，由于 y 想要到达 x 的父亲必须经过 (x,y) 这条边，所以删去这条边，图不连通）。
特别需要注意，因为遍历的是无向图，所以从每个点 x 出发，总能访问到它的父节点 fa。根据 low 的计算方法，(x,fa) 属于搜索树上的边，且 fa 不是 x 的子节点，故不能用 fa 的时间戳来更新 low[x]。
如果仅记录每个节点的父节点，会无法处理重边的情况。当 x 与 fa 之间有多条边时，(x,fa) 一定不是桥。在这些重复的边中，只有一条算是“搜索树上的边”，其他的几条都不算。故有重边时，dfn[fa] 能用来更新 low[x]。
改为 记录“递归进入每个节点的边的编号”。编号可认为是边在邻接表中存储的下标位置。把无向图的每一条边看做双向边，成对 存储在下标里。若沿着编号为 i 的边递归进入了节点 x，则忽略从 x 出发的编号 i xor 1 的边，通过其他边计算 low[x] 即可。
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+5; int n,m,x,y,cnt=1,hd[N],to[N<<1],nxt[N<<1],dfn[N],low[N],num; //注意 cnt 要初始化为 1。对于非负整数 n：当 n 为偶数时，n xor 1=n+1；当 n 为奇数时，n xor 1=n-1。因此，(0,1)(2,3)(4,5)... 关于 xor 1 运算构成“成对变换”。我们把无向图的正反方向的边分别存储在邻接表数组的第 n 与 n+1 位置（其中 n 为偶数）。由于 add 函数中写的是 ++cnt，并且我们刚刚所说的 n 为偶数，因此 cnt 要初始化为 1。 bool g[N<<1]; void add(int x,int y){ to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt; } void tarjan(int x,int fa){ //这里的 fa 不是 x 的父亲，是指递归进入每个节点的边的编号（边在邻接表中存储的下标位置），变量名是我瞎起的 qwq dfn[x]=low[x]=++num; for(int i=hd[x];i;i=nxt[i]){ int y=to[i]; if(!dfn[y]){ tarjan(y,i); low[x]=min(low[x],low[y]); if(low[y]>dfn[x]) g[i]=g[i^1]=1; } else if(i!=(fa^1)) low[x]=min(low[x],dfn[y]); } } signed main(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++){ scanf("%lld%lld",&x,&y); add(x,y),add(y,x); } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0); for(int i=2;i<cnt;i+=2) if(g[i]) printf("%lld %lld ",to[i^1],to[i]); //输出的为割边 return 0; }
二、Tarjan 求割点
对于无向图 G，如果删除某个点 x 后，连通分量数目增加，则称点 x 是图 G 的割点。
判断割点：若 x 不是搜索树的根结点（深度优先遍历的起点），则 x 是割点当且仅当搜索树上存在 x 的一个子节点 y，满足：dfn[x]≤low[y]。特别地，若 x 是搜索树的根结点，则 x 是割点当且仅当搜索树上出在至少两个子节点 y1,y2 满足上述条件。
具体来说，我们可以把在结点 x 为根的子树（不包括 x）的点集即为 S(x)，把不在 x 为根的子树中的点集即为 T(x)。对于某个点 x，若 S(x) 中存在至少一点 y，满足 y 与 T(x) 之间没有任何边，则 x 是割点。我们可以利用 Tarjan 算法记录 dfn[x] 和 low[x]。于是问题转化成，节点 x 是否存在一个儿子 y，使得 low[y]≥dfn[x]。
我们只需一次 DFS 即可，总时间复杂度 O(n+m)。
因为割点的判定是小于等于号，所以在求个割点时，不必考虑父节点和重边的问题，从 x 出发能访问到的所有点的时间戳都可以用来更新 low[x]。
参考程序如下：
#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+5; int n,m,x,y,cnt=1,hd[N],to[N<<1],nxt[N<<1],dfn[N],low[N],num,root; bool g[N]; void add(int x,int y){ to[++cnt]=y,nxt[cnt]=hd[x],hd[x]=cnt; } void tarjan(int x){ dfn[x]=low[x]=++num; int flag=0; for(int i=hd[x];i;i=nxt[i]){ int y=to[i]; if(!dfn[y]){ tarjan(y),low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ flag++; if(x!=root||flag>1) g[x]=1; //割点判定法则 } } else low[x]=min(low[x],dfn[y]); } } signed main(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++){ scanf("%lld%lld",&x,&y); if(x==y) continue; add(x,y),add(y,x); } for(int i=1;i<=n;i++) if(!dfn[i]) root=i,tarjan(i); for(int i=1;i<=n;i++) if(g[i]) printf("%lld ",i); //输出的是割点 return 0; }