❤性❤感❤代❤码❤在线求调
查看原帖
❤性❤感❤代❤码❤在线求调
809765
Limitless_lmw楼主2024/11/29 18:04

rt

#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+5;
int head[maxn], nxt[maxn], to[maxn], tot;

inline void add_V(int b,int e){
	nxt[++tot] = head[b];
	to[head[b] = tot] = e;
	return ;
}

int dfn[maxn], low[maxn], st[maxn], top;
bool ins[maxn];
int cnt, idx, bel[maxn];
pair<int,int> ans[maxn];
int anscnt;
int n,m;

int dfs(int u, int lst){
	low[u] = dfn[u] = ++cnt;
	st[++top] = u;
	for(int i = head[i]; i; i = nxt[i]){
		if(i == (lst ^ 1)) continue;
		if(!dfn[to[i]]){
			dfs(to[i], i);
			low[u] = min(low[u],low[to[i]]);
			if(low[to[i]]>dfn[u]) ans[anscnt++] = make_pair(min(u,to[i]),max(u,to[i]));
		}else low[u] = min(low[u],dfn[to[i]]);
	}
	if(low[u] == dfn[u]){
		int v; ++idx;
		do{
			v = st[top--];
			bel[v] = idx;
		}while(u ^ v);
	}
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i = 1,u,v; i<=m; i++){
		scanf("%d %d",&u,&v);
		add_V(u,v),add_V(v,u);
	}
	for(int i = 1; i<=n; i++){
		if(!dfn[i]) dfs(i,-1);
	}
	sort(ans,ans+anscnt);
	for(int i = 0; i<anscnt; i++) cout<<ans[i].first<<" "<<ans[i].second<<'\n';
	return 0;
}

现在可以确定的是她认为每一单点都是一个 v-DCC 呢

2024/11/29 18:04
加载中...