仅能过样例1和样例2求调
查看原帖
仅能过样例1和样例2求调
1155519
Exusiaiii楼主2024/11/5 21:40

仅能过样例1和样例2,求调。

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
const int M=5e6+5;
int bri[N],dfn[N],low[N],n,m,p[N],edge_num,dcc[N],vis[N],cnt,u,v,head[N],tot;
vector<int>ans[M];
struct node{
	int from;
	int to;
	int next;
}edge[M];
void add(int from,int to){
	edge[++edge_num].next=head[from];
	edge[edge_num].to=to;
	edge[edge_num].from=from;
	head[from]=edge_num;
}
void tarjan(int x,int in_edge){
	dfn[x]=low[x]=++tot;
	for(int i=head[x];i;i=edge[i].next){
		int y=edge[i].to;
		if(!dfn[y]){
			tarjan(y,i);
			low[x]=min(low[x],low[y]);
			if(dfn[x]<low[y])	bri[i]=bri[i^1]=true;
		}
		else if(i!=(in_edge^1)){
			low[x]=min(low[x],dfn[y]);
		}
	}
}
void dfs(int x){
	vis[x]=1;
	ans[cnt].push_back(x);
	for(int i=head[x];i;i=edge[i].next){
		if(bri[i])	continue;
		int v=edge[i].to;
		if(!vis[v]){
			dfs(v);
		}
	}
	
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])	tarjan(i,i);
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
			cnt++;
		}
	}
	cout<<cnt<<endl;
	for(int i=0;i<cnt;i++){
		cout<<ans[i].size()<<" ";
		for(int v:ans[i]){
			cout<<v<<" ";
		}
		cout<<endl;
	}
}
2024/11/5 21:40
加载中...