/*
tarjan算法求割边
割边的概念:有连通图G,e是其中一条边,如果G-e(这是减号,当时看书理解了好久)
是不连通的,则称边e是图G的一条割边
tarjan算法:若u的子节点v没有反向边返回u及其祖先,或v的子孙没有反向边返回u及
其祖先,即low[v]>dfn[u],则u到v这条边是割边,但从v开始搜索结点的时候要把它
的父节点排除在外,即反向父亲的反向边是不能用的
*/
#include<bits/stdc++.h>
#define pii pair<int,int> 
using namespace std;
int n,m,dfn[5005],low[5005],times=0;
vector<int> g[5005];
priority_queue<pii,vector<pii>,greater<pii> >q;
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++times;
    for(auto& v:g[u])
    {
        if(v==fa)continue;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<low[v])
                q.push(make_pair(min(u,v),max(u,v)));
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    tarjan(1,1);
    while(!q.empty())
    {
        cout<<q.top().first<<' '<<q.top().second<<endl;
        q.pop();
    }
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
2206
难度
9
分类
(无)
标签
递交数
4
已通过
3
通过率
75%
被复制
2
上传者