Tarjon悬2关代码求调
查看原帖
Tarjon悬2关代码求调
373198
WhileTrueRP楼主2023/12/23 14:58
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
const int M = 2e6+5;
int head[N],nxt[M<<1],to[M<<1];
int dfn[N],low[N];
bool vis[N],vvis[N];
vector<int> ans[N];
int cnt_ans = 0;
int tot = 0,cnt = 0,root;
void add(int x,int y){
	nxt[++tot] = head[x];
	to[tot] = y;
	head[x] = tot;
	
	nxt[++tot] = head[y];
	to[tot] = x;
	head[y] = tot;
}
void tarjon(int x,int last_edge){
	dfn[x] = low[x] = ++cnt;
	for(int i=head[x];i;i=nxt[i]){
		int y = to[i];
		if(!dfn[y]){
			tarjon(y,i);
			low[x] = min(low[x],low[y]);
			if(low[y] > dfn[x]){
				printf("%d %d\n",x,y);
				vis[i] = true;
				vis[i^1] = true;
			}
		}else if(i != (last_edge^1)){
			low[x] = min(low[x],dfn[y]);
		}
	}
}
void dfs(int x){
	ans[cnt_ans].push_back(x);
	for(int i=head[x];i;i=nxt[i]){
		int y = to[i];
		if(vis[i] || vvis[y]){
			continue;
		}
		vvis[y] = true;
		dfs(y);
	}
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			root = i;
			tarjon(i,-1);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vvis[i]){
			cnt_ans ++;
			vvis[i] = true;
			dfs(i);
		}
	}
	printf("%d\n",cnt_ans);
	for(int i=1;i<=cnt_ans;i++){
		printf("%d ",ans[i].size());
		for(int j=0;j<ans[i].size();j++){
			printf("%d ",ans[i][j]);
		}
		puts("");
	}
}
2023/12/23 14:58
加载中...