写挂了,不知道为啥(也许是重边吧),代码在线求调
查看原帖
写挂了,不知道为啥(也许是重边吧),代码在线求调
1164775
Jadonyzx楼主2024/2/22 20:18
#include<bits/stdc++.h>
#define int long long
#define maxn 500010
#define maxm 2000010
using namespace std;
int n,m;
int dfn[maxn],low[maxn],vis[maxn],CNT;
int dfcnt,cnt,bcccnt;
vector<int>bcc[maxn];
struct EDGE{
	int to;
	bool bridge,if_cb;
};
struct Node{
	int from,to;
	bool if_cb;
}node[maxm*2];
vector<EDGE>edge[maxn];
void addedge(Node aaa){
	edge[aaa.from].push_back({aaa.to,false,aaa.if_cb});
	return;
}
void Tarjan(int id,int father){
	dfn[id]=low[id]=++dfcnt;
	int child;
	for(int j = 0;j < edge[id].size();++j){
		child=edge[id][j].to;
		if(dfn[child]&&child!=father) low[id]=min(low[id],dfn[child]);
		if(!dfn[child])
		{
			Tarjan(child,id);
			if(low[child]>dfn[id]){
				if(!edge[id][j].if_cb)
					edge[id][j].bridge=true;
			}
			low[id]=min(low[id],low[child]);
		}
		
	}
	return;
}
void dfs(int id){
	vis[id]=1;
	bcc[bcccnt].push_back(id);
	for(int ioi=0;ioi<edge[id].size();++ioi){
		if(!vis[edge[id][ioi].to]&&!edge[id][ioi].bridge) dfs(edge[id][ioi].to);
	}
	return;
}
bool cmp(Node A,Node B){
	if(A.from!=B.from) return A.from<B.from;
	return A.to<B.to;
}
signed main(){
	cin>>n>>m;
	for(int i = 1;i <= m;++i){
		int u,v;
		cin>>u>>v;
		node[++CNT].from=u;
		node[CNT].to=v;
		node[CNT].if_cb=false;
		if(u!=v){
			node[++CNT].from=v;
			node[CNT].to=u;
			node[CNT].if_cb=false;
		}
	}
	sort(node+1,node+1+CNT,cmp);
	Node past=node[1];
	for(int i = 2;i <= CNT;++i){
		Node now=node[i];
		if(now.from==past.from&&now.to==past.to){
			node[i-1].if_cb=true;node[i].if_cb=true;
		}
		past=now;
	}
	for(int i = 1;i <= CNT;++i){
		addedge(node[i]);
	}
	for(int i = 1;i <= n;++i)
		if(!dfn[i]) Tarjan(i,i);
	for(int i = 1;i <= n;++i)
	{
		if(!vis[i]) ++bcccnt,dfs(i);
	}
	cout<<bcccnt<<'\n';
	for(int i=1;i <= bcccnt;++i){
		cout<<bcc[i].size()<<' ';
		for(int j = 0;j < bcc[i].size();++j)
			cout<<bcc[i][j]<<' ';
		cout<<'\n';
	}
	return 0;
}
2024/2/22 20:18
加载中...