60分,WA2,4求助大佬
查看原帖
60分,WA2,4求助大佬
792372
zhanjidaihao666123楼主2023/12/10 20:15
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,cnt,num,ans,head[200010];
int low[210000],dfn[210000],p[200100];
struct Edge{
	int to;
	int next;
}edge[210000];
struct Node{
	int x;
	int y;
}node[550000];
bool cmp(Node x,Node y){
	if(x.x!=y.x){
		return x.x<y.x;
	}
	else{
		return x.y<x.y;
	}
}
void add(int u,int v){
	edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
}
void tarjan(int u,int fa){
	low[u]=dfn[u]=++num;//赋初值,初值dfs到达点的次序 
	for(int i=head[u];i!=0;i=edge[i].next){
		int v=edge[i].to;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]){
				node[++ans].x=u;
				node[ans].y=v;
			}
		}
		else if(v!=fa){
			low[u]=min(low[u],dfn[v]);
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(dfn[i]==0){
			tarjan(1,1);
		}
	}
	sort(node+1,node+ans+1,cmp);
	for(int i=1;i<=ans;i++){
		cout<<node[i].x<<" "<<node[i].y<<endl;
	}
}
2023/12/10 20:15
加载中...