dfs60分求助#4#5WA
  • 板块P1656 炸铁路
  • 楼主wj2008
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/10 11:01
  • 上次更新2024/7/10 12:13:59
查看原帖
dfs60分求助#4#5WA
947041
wj2008楼主2024/7/10 11:01
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
vector<int> a[101010];
int cnt=0;
int dfn[101010],c[101010],check[101010];
int fa[101010];
struct ac{
	int l,r;
}g[101010];
int sum=0;
void dfs(int x){
	cnt++;
	dfn[x]=cnt,c[x]=cnt;
	check[x]=1;
	bool gh=false;
	for(int i=0;i<a[x].size();i++){
		if(a[x][i]==fa[x]&&gh==false){
			gh=true;//防止重边
			continue;
		}
		
		if(check[a[x][i]]==0){
			fa[a[x][i]]=x;
			check[a[x][i]]=1;
			dfs(a[x][i]);
			c[x]=min(c[x],c[a[x][i]]);
			if(c[a[x][i]]>c[x]){
				g[++sum].l=min(a[x][i],x);
				g[sum].r=max(a[x][i],x);
			}
		//	c[x]=min(c[x],c[a[x][i]]);
		}else{
			c[x]=min(c[x],c[a[x][i]]);
		}
	
	}
}
bool cmp(ac x,ac y){
	if(x.l==y.l){
		return x.r<y.r;
	}
	return x.l<y.l;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
	    int x,y;
	    cin>>x>>y;
	    a[x].push_back(y);
	    a[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(check[i]==0){
			dfs(i);
		}
	}
	system("cls");
	sort(g+1,g+1+sum,cmp);
	for(int i=1;i<=sum;i++){
		cout<<g[i].l<<" "<<g[i].r<<endl;
	}
}
2024/7/10 11:01
加载中...