题解--P1656
楼顶tarjan不太详细啊，我来讲详细一点吧
先上代码，代码中有讲解
#include <bits/stdc++.h>
using namespace std;
int maps[151][151];//邻接矩阵，简单易懂
struct Edge {
int x,y;
} E[5001];//这是存答案的，用邻接表存，应该不用解释
int dfn[151],low[151],n,m,id,cnt,f[151];/*这些数组的含义：
dfn:
{
下标：点编号
内存的值：深度优先搜索时第几个遍历
}
low:
{
下标：点编号
内存的值：这个点能通过它的子孙到达的dfn值最小的点的dfn
}
f:
{
下标：点标号
内存的值：它遍历的上一个点
}
变量的含义：
n:结点个数
m:边个数
id:用于dfn标记
cnt:用于邻接表存图
*/
bool cmp(struct Edge a,struct Edge b) {
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}//因题目要求，边要排序，要做这道题的人应该都知道cmp
void addEdge(int x,int y) {
E[++cnt].x=x;
E[cnt].y=y;
}//addedge函数，存入邻接表
void tarjan(int x) {
int c=0,y;
dfn[x]=low[x]=++id;
for(register int i=1; i<=n; i++) {
if(!maps[x][i])continue;//首先要有边
y=i;//处理对象
if(dfn[y]&&y!=f[x])low[x]=min(low[x],dfn[y]);//如果是它爸爸，割边就没有用了，好好理解
if(!dfn[y]) {//如果找到祖先还有什么用呢
f[y]=x;//不是祖先就认爸爸
tarjan(y);//dfs过程
low[x]=min(low[x],low[y]);//回溯时带着爸爸更新low
if(low[y]>dfn[x])addEdge(x,y);//是割边，就加入吧
}
}
}//tarjan部分，证明在下面
int main() {
int x,y;
cin>>n>>m;
for(register int i=1; i<=m; i++) {
cin>>x>>y;
maps[x][y]=maps[y][x]=1;//存边
}
for(register int i=1; i<=n; i++) {
if(!dfn[i])tarjan(i);//tarjan
}
sort(E+1,E+cnt2+1,cmp);//sort大法好
for(register int i=1; i<=cnt; i++) {
cout<<min(E[i].x,E[i].y)<<' '<<max(E[i].x,E[i].y)<<endl;//输出
}
return 0;//程序结束了，证明开始了
}
这是一个图 图中有边
深度优先遍历后（描绿的边为遍历过的边）
dfn值和f值已固定
low值暂时为它自己
接下来我们看看能不能有边回到它的祖先但不是它的父亲的结点
于是我们继续回溯（因为搜完了返回）
发现结点7可以回到结点2
于是它的low值立刻被改为2
一路上它的除了1和2的其他祖先low值都被改成了2
后面搜索结束
我们发现2-3-4-5-6-7这些结点都有至少两条完全不同的路通往这些结点（2、3、4、5、6、7）中的其它结点（也就是点双联通）
但是1、8不是
我们发现图中的割边（把这条边去掉，图不联通）有几条呢？
很明显有（1-2）、（7-8）两条
我们来看看它们low值有什么关系呢？
我们发现祖先的low值都比子孙的小
也就是说子孙不能到达祖先以上的结点，除了这条边就再无去路
如果这条边没了呢？子孙岂不是不能到达祖先及其以上的点咯。
这条边就可以把图分成祖先和子孙两个不联通的区域，这就是割边