本蒟蒻女生代码求条 QaQ
查看原帖
本蒟蒻女生代码求条 QaQ
959185
kinglf楼主2024/7/15 19:20

刚刚学习点双,勿喷.

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,idx,top,vdcccnt,root,cut[N],cnt[N],vdcc[N],stk[N],dfn[N],low[N];
vector <int> G[N],ans[N];
void dfs(int x){
	dfn[x]=low[x]=++idx;
	stk[++top]=x;
	if (x==root&&!G[x].size()){
		vdcccnt++;
		top--;
		ans[vdcccnt].push_back(x);
		return ;
	}
	int son=0;
	for (int i=0;i<G[x].size();i++){
		int y=G[x][i];
		if (!dfn[y]){
			dfs(y);
			son++;
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				if (x!=root||son>1) cut[x]=1;
				vdcccnt++;
				int tem;
				do{
					tem=stk[top--];
					ans[vdcccnt].push_back(tem);
				}while (tem!=x);//错误 
				stk[++top]=x;//错误 
				//while (tem!=y);//正确 
				//ans[vdcccnt].push_back(x);//正确 
			}
		}
		else low[x]=min(low[x],dfn[y]);
	}
}
int main(){
	scanf ("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int u,v;
		scanf ("%d%d",&u,&v);
		if (u==v) continue;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i=1;i<=n;i++)
		if (!dfn[i]){
			root=i;
			dfs(i);
		}
	printf ("%d\n",vdcccnt);
	for (int i=1;i<=vdcccnt;i++){
		printf ("%d ",ans[i].size());
		for (int j=0;j<ans[i].size();j++)
			printf ("%d ",ans[i][j]);
		puts("");
	}
	

	return 0;
}

注释处存疑,两种写法看起来差不多,但一种48分,一种100分{{|└(>o<)┘|}}?!

2024/7/15 19:20
加载中...