P1656 bombing Railway

Title Description

A The country sent a general uim, Yes B The United Nations undertakes strategic measures , In order to save the people who are painted with charcoal .

B State-owned  nn  Cities , These cities are connected by rail . Any two cities can be reached directly or indirectly by rail .

uim After discovering that some of the railways were destroyed , Two cities can't reach each other by rail . Such a railway is called key road.

uim In order to paralyze the country's logistics system as soon as possible , Hope to blow up the railway , In order to achieve the effect that two cities cannot reach each other by railway .

However , Only one shell （A The Congress won't give money ）. therefore , Which railway can he bomb ？

Input format

first line  nn,m (1 \leq n\leq 150m(1≤n≤150,1 \leq m \leq 5000)1≤m≤5000), They are  nn  Cities , in total  mm  A railway .

following  mm  That's ok , Two integers per line  a, ba,b, Representing City  aa  And the city  bb  There's a direct rail connection between them .

Output format

The output has several lines .

Each line contains two numbers  aa,bb, among  a<ba<b, Express  <a,b><a,b>  yes key road.

Please note that ： When the output , All number pairs  <a,b><a,b>  Must follow  aa  Sort output from small to large ; If aa  identical , According to  bb  Sort from small to large .

I/o sample

Input #1 Copy

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

Output #1 Copy

1 2
5 6

This question examines Cut edge of graph

The steps of edge cutting and point cutting of graph are almost the same , There is only one difference in the code implementation

I wrote in this blog about the cutting point and edge of graph

（ Not yet I'll post the link after I write it ）

This problem is a typical edge cutting template problem of graph , The train of thought is ： Depth first traverses every point , Depth first traversal to point u when , Suppose there are vertices in the graph v It is a point that has not been visited , Judgment vertex v Can I go back to the point I visited before （ Including some u）, The way to judge is ： To the summit v Do another depth first traversal , But this traversal is not allowed to pass through vertices u, If vertex v You can't go back to your ancestors , There is no other way back u, that u-v This side is the cut side .

Another special feature of this question is the output time , All number pairs <a,b>  Must follow  a  Sort output from small to large ; If a identical , According to  b  Sort from small to large . You need to store the edge cutting with a structure array , Then sort according to this rule .

ac Code

#include<bits/stdc++.h>
using namespace std;
#define N 160
int n,m,x,y;
int v[N][N];
int num[N],low[N],flag[N],dex,o;
struct
{
    int x,y;
} ans[N];

void dfs(int cur,int father)
{
    dex++;
    num[cur]=dex;
    low[cur]=dex;
    for(int i=1; i<=n; i++)
    {
        if(v[cur][i] == 1)
        {
            if(num[i] == 0)
            {
                dfs(i,cur);
                low[cur]=min(low[i],low[cur]);
                if(low[i]>num[cur])
                {
                    ans[o].x=cur;
                    ans[o].y=i;
                    o++;
                }
            }
            else if(i != father)
            {
                low[cur]=min(low[cur],num[i]);
            }
        }
    }
}
int main()
{

    cin>>n>>m;
    while(m--)
    {
        cin>>x>>y;
        v[x][y]=1;
        v[y][x]=1;
    }
    int root=1;
    dfs(1,root);
    
    /// Sort 
    for(int i=0; i<o-1; i++)
        for(int j=i+1; j<o; j++)
           {
              if(ans[j].x<ans[i].x)
                {
                   int temp=ans[j].x;ans[j].x=ans[i].x;ans[i].x=temp;
                       temp=ans[j].y;ans[j].y=ans[i].y;ans[i].y=temp;
                }
              else if(ans[j].x == ans[i].x)
                     {
                        if(ans[j].y<ans[i].y)
                        {
                           int temp=ans[j].x;ans[j].x=ans[i].x;ans[i].x=temp;
                           temp=ans[j].y;ans[j].y=ans[i].y;ans[i].y=temp;
                         }
                      }
           }
    for(int i=0; i<o; i++)
        cout<<ans[i].x<<" "<<ans[i].y<<endl;
    return 0;
}