- 考验(proof)
- 2024-05-14 20:46:54 @
/*
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
- 上传者