75分求助
查看原帖
75分求助
930117
Lyy450605楼主2023/8/10 22:00

求调试,最后两个点 WA\color{red}{WA} ,显示连通分量数比答案大一千左右。qwq ,玄关

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

const int N=1e6+10;
const int M=2e6+10;
const int INF=0x3f3f3f3f;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

struct LINK{//结构体
	struct Node{
		int to;
		int next;
	};
	Node edge[M<<1]; int head[N],cnt;
	LINK (){//构造函数
		cnt=1;//用异或
	}
	inline void Insert(int from,int to){
		++cnt;
		edge[cnt].to=to;
		edge[cnt].next=head[from]; head[from]=cnt;
	}
};

int n,m,a,b;  LINK G;
int low[N],dfn[N],dfcnt; bitset<M> vis1; bitset<N> vis2;
vector<int> ans[N];  int dcc;

void tarjen(int cur,int last){
	dfn[cur]=low[cur]=++dfcnt;
	for(int i=G.head[cur];i;i=G.edge[i].next){
		int to=G.edge[i].to;
		if(to==last) continue;//
		if(!dfn[to]){
			tarjen(to,cur);
			low[cur]=min(low[cur],low[to]);
			if(low[to]>dfn[cur]){//
				vis1[i]=1;
				vis1[i^1]=1;
			}
		}
		else low[cur]=min(low[cur],dfn[to]);
	}
}
void dfs(int cur,int last){
	vis2[cur]=1;
	ans[dcc].push_back(cur);
	for(int i=G.head[cur];i;i=G.edge[i].next){
		int to=G.edge[i].to;
		if(vis2[to]||vis1[i]) continue;
		dfs(to,cur);
	}
}

signed main(){//想法:删除桥
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a>>b;
		if(a==b) continue;
		G.Insert(a,b);
		G.Insert(b,a);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjen(i,0);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis2[i]){
			dcc++;
			dfs(i,0);
		}
	}
	cout<<dcc<<"\n";
	for(int i=1;i<=dcc;i++){
		cout<<ans[i].size()<<" ";
		for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";
		cout<<"\n";
	}
	return 0;
}
2023/8/10 22:00
加载中...