为什么呢
  • 板块P1656 炸铁路
  • 楼主liuchijun
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/1/21 14:26
  • 上次更新2025/1/21 16:20:58
查看原帖
为什么呢
1094880
liuchijun楼主2025/1/21 14:26

全RE

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mkpr make_pair
using namespace std;
const int maxn=1e5+10;
int head[maxn],nxt[maxn<<1],to[maxn<<1],tot=1;
void addedge(int b,int e){
	nxt[++tot]=head[b],to[head[b]=tot]=e;
	nxt[++tot]=head[e],to[head[e]=tot]=b;
}
pii edge[maxn];
int dfn[maxn],low[maxn],st[maxn],top;
int cnt,idx,bel[maxn],anscnt=0;
void dfs(int u,int lst){
	low[u]=dfn[u]=++cnt;
	st[++top]=u;
	for(int i=head[u];i;i=nxt[i])
	{
		if(i!=(lst^1)){
			int v=to[i];
			if(!dfn[v]){
				dfs(v,i);
				low[u]=min(low[u],low[v]);
				if(low[v]>dfn[u])
					edge[anscnt++]=mkpr(min(u,v),max(u,v));
			}
			else
				low[u]=min(low[u],dfn[v]);
		}
		if(low[u]==dfn[u]){
			int v;
			++idx;
			do{
				v=st[top--];
				bel[v]=idx;
			}while(v!=u);
		}
	}
}
bool cmp(pii x,pii y)
{
	if(x.first!=y.first)return x.first<y.first;
	return x.second<y.second;
}
int main()
{
	int n,m;
	ios::sync_with_stdio(false);
	std::cin.tie(0),std::cout.tie(0);
//	freopen("destroy.in","r",stdin);
//	freopen("destroy.out","w",stdout);
	cin>>n>>m;
	for(int i=0,a,b;i<m;i++)
		cin>>a>>b,addedge(a,b);
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			dfs(i,-1);
	sort(edge,edge+anscnt);
	for(int i=0;i<anscnt;i++)
		cout<<edge[i].first<<' '<<edge[i].second<<'\n';
	return 0;
}

2025/1/21 14:26
加载中...