RE求调
查看原帖
RE求调
250097
BaYueXiang楼主2025/1/19 22:06
#include<bits/stdc++.h>
using namespace std;
int n,m,h[2000],dfn[2000],low[2000],st[2000],top,color[2000],cn,th;
set<pair<int,int> >ans;
set<pair<int,int> >::iterator p;
struct node{
	int u,v,nxt;
}edge[10010];
void ae(int a,int u,int v) {
	edge[a].u=u;
	edge[a].v=v;
	edge[a].nxt=h[u];
	h[u]=a;
}
void dfs(int u,int fa) {
	th++;
	low[u]=dfn[u]=th;
//	cout <<th<<" "<<u<<endl;
	st[top]=u;
	top++;
	for (int a=h[u];a;a=edge[a].nxt) {
		int v=edge[a].v;
		if (v==fa) continue;
//		cout <<u<<"---------"<<v<<endl;
		if (!dfn[v]) {
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			if (dfn[u]<low[v]) 
				ans.insert(make_pair(min(u,v),max(u,v)));
		}
		else low[u]=min(low[u],dfn[v]);
	}
	if (dfn[u]==low[u]) {
		int v;
		cn++;
		do{
			v=st[top];
			top--;
			color[v]=cn;
		} while(v!=u);
	}
}
int main () {
	cin >>n>>m;
	for (int a=1;a<=m;a++) {
		int u,v;
		cin >>u>>v;
		ae(a*2-1,u,v);
		ae(2*a,v,u);
	}
	dfs(1,0);
//	cout <<endl;
	for (p=ans.begin();p!=ans.end();p++) {
		cout <<(p->first)<<" "<<(p->second)<<endl;
	}
	return 0;
}

22 个测试点会莫名其妙的 RERE,但是把数据下载下来本地运行没有问题。

2025/1/19 22:06
加载中...