{part2}DFN+LOW（tarjan）割边

首先非树边肯定不是割边，因为去掉它DFS树不受影响，只要还能生成一棵DFS树那么图就是连通的。

然后割掉一条树边只可能造成一个点与它的父亲不连通。

那好办，也就是说这个以这个点为根的子树就是上面所说的满足条件的子树，也就是它没有返祖边，不过要注意的是，这里的low被重定义为每个点沿着除了父边之外的所有边能访问到的最小的dfn值，请结合割点割边的含义以及上面加粗的字体理解这句话，差别其实就在于x到父亲可能会有重边。

其他的都一样，核心还是判断x是否是这样的一棵子树。

直接上例题：

天凯是苏联的总书记。苏联有n个城市，某些城市之间修筑了公路。任意两个城市都可以通过公路直接或者间接到达。
天凯发现有些公路被毁坏之后会造成某两个城市之间无法互相通过公路到达。这样的公路就被称为dangerous pavement。
为了防止美帝国对dangerous pavement进行轰炸，造成某些城市的地面运输中断，天凯决定在所有的dangerous pavement驻扎重兵。可是到底哪些是dangerous pavement呢？你的任务就是找出所有这样的公路。

第一行n，m(1<=n<=150, 1<=m<=5000)，分别表示有n个城市，总共m条公路。
以下m行每行两个整数a, b，表示城市a和城市b之间修筑了直接的公路

6 6
1 2
2 3
2 4
3 5
4 5
5 6

输出有若干行。每行包含两个数字a,b(a<b)，表示<a,b>是dangerous pavement。请注意：输出时，所有的数对<a,b>必须按照a从小到大排序输出；如果a相同，则根据b从小到大排序。

1 2
5 6

cpp：

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<iomanip>

 #include<queue>

 #include<vector>

 #include<ctime>

 using namespace std;

 const int maxn=;

 int len=,linkk[maxn];

 int n,m,ind=,top=;

 int dfn[maxn],low[maxn];

 struct node

 {

     int x,y;

 }e[maxn],ans[maxn];

 void init(int xx,int yy)

 {

     e[++len].y=linkk[xx];linkk[xx]=len;

     e[len].x=yy;

 }

 void dfnlow(int x,int p=)

 {

     int y;

     dfn[x]=low[x]=++ind;

     for(int i=linkk[x];i;i=e[i].y)

     {

         y=e[i].x;

         if(!dfn[y])

         {

             dfnlow(y,x);

             if(low[y]<low[x])

                 low[x]=low[y];

             if(dfn[x]<low[y])

                 ans[++top].x=x,ans[top].y=y;

         }

         else if(dfn[y]<low[x]&&y!=p)

             low[x]=dfn[y];

     }

 }

 bool mys(node a,node b)

 {

     return a.x<b.x||a.x==b.x&&a.y<b.y;

 }

 int main()

 {

     /*freopen("2.in","r",stdin);

     freopen("2.out","w",stdout);*/

     ios::sync_with_stdio(false);

     cin>>n>>m;

     for(int i=;i<=m;i++)

     {

         int a,b;

         cin>>a>>b;

         init(a,b);

         init(b,a);

     }

     for(int i=;i<=n;i++)

         if(!dfn[i])

         {

             dfnlow(i,i);

         }

     sort(ans+,ans++top,mys);

     for(int i=;i<=top;i++)

         cout<<ans[i].x<<" "<<ans[i].y<<endl;

     return ;

 }

巴特西

{part2}DFN+LOW（tarjan）割边

最新文章

热门文章