求助:为什么点双要判自环
查看原帖
求助:为什么点双要判自环
253936
simonG楼主2023/3/16 09:17

不判过不了。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,M=2e6+10;
int head[N],ver[2*M],nxt[2*M],tot=1;
int n,m,dfn[N],low[N],num,rt;
int dcc,cut[N];
int stk[N],tp;
vector<int> DCC[N];
void addedge(int x,int y) {
	ver[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
void tarjan(int u,int in_edge) {
	dfn[u]=low[u]=++num;
	int flag=0;
	if(u==rt&&head[u]==0) {
		++dcc;
		DCC[dcc].push_back(u);
		return ;
	}
	stk[++tp]=u;
	for(int i=head[u]; i; i=nxt[i]) {
		int v=ver[i];
		if(!dfn[v]) {
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]) {
				flag++;
				if(u!=rt||flag>1) cut[u]=1;
				dcc++;
				int z;
				do {
					z=stk[tp--];
					DCC[dcc].push_back(z);
				} while(z!=v);
				DCC[dcc].push_back(u);
			}
		} else if(i!=(in_edge^1))	
			low[u]=min(low[u],dfn[v]);
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1,u,v; i<=m; i++) {
		scanf("%d%d",&u,&v);
//		if(u==v) continue;
		addedge(u,v); addedge(v,u);
	}
	for(int i=1; i<=n; i++)
		if(!dfn[i]) {
			rt=i; tarjan(rt,0);
		}
	printf("%d\n",dcc);
	for(int i=1; i<=dcc; i++) {
		printf("%d ",DCC[i].size());
		for(int j=0; j<DCC[i].size(); j++) {
			printf("%d ",DCC[i][j]);
		}
		puts("");
	}
	return 0;
}
2023/3/16 09:17
加载中...