全TLE求条
查看原帖
全TLE求条
989143
Nahida_Official楼主2025/1/10 16:12
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MANX=2000010;
int tot=1,n,m;
int to[MANX],nxt[MANX],head[MANX];
int dfn[MANX],low[MANX],times;
bool bridge[MANX];
int id[MANX],dcc=0;
vector<int> d[MANX];
void add(int x,int y){
	to[++tot]=y;
	nxt[tot]=head[x];
	head[x]=tot;
}
int tarjan(int x,int edge){
	dfn[x]=low[x]=++times;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y]){
				bridge[i]=bridge[i^1]=true;
			}
		}
		else if(i!=(edge^1)) low[x]=min(low[x],dfn[y]);
	}
}
void dfs(int x){
	id[x]=dcc;
	d[dcc].push_back(x);
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(id[y] || bridge[i]) continue;
		dfs(y);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		add(x,y); add(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i,0);
	}
	for(int i=1;i<=n;i++){
		if(!id[i]){
			dcc++;
			dfs(i);
		} 
	}
	cout<<dcc<<"\n";
	for(int i=1;i<=dcc;i++){
		int len=d[i].size();
		cout<<len<<" ";
		for(int j=0;j<len;j++){
			cout<<d[i][j]<<" "; 
		}
		cout<<"\n";
	}
	return 0;
}
2025/1/10 16:12
加载中...