样例三过不了求调
查看原帖
样例三过不了求调
990478
CPlusPlus_xiang楼主2024/10/23 11:11

第三个样例不仅少算了一个连通分量,甚至有一个连通分量的点输出0,真的找不到问题了求调

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

const int N = 1000100;
int n,m;
int head[N],nextx[N],to[N],num;

int dfn[N],low[N],ins[N],s[N],tot,root,top;//s为栈储存当前的联通分量的元素,ins标记当前元素是否在栈内部 ,tot为dfs的顺序

int cnt;//为连通块的个数
vector<int> f[N * 2];//储存每一个前连通分量的信息 
int sortt[N];

void add(int start,int end){
	to[++num] = end;
	nextx[num] = head[start];
	head[start] = num;
}

void tarjan(int noww){
	dfn[noww] = ++tot;
	low[noww] = tot;//初始化low
	s[++top] = noww;
	ins[noww] = 1;
	if(noww == root && head[noww] == 0){
		f[++cnt].push_back(noww);//为根节点且没有边,那就放入新的强连通分量数组内 
		return;
	} 
	for(int i = head[noww];i != 0;i = nextx[i]){
		int son = to[i];
		if(dfn[son] == 0){
			tarjan(son);
			low[noww] = min(low[noww],low[son]);
			if(low[son] >= dfn[noww]){
				cnt++;//当前点为割点,连通块数量加一
				int z,topp = top;
				do{
					z = s[top--];
					ins[z] = 0;//清除标记
					f[cnt].push_back(z); 
				}while(z != son);
				f[cnt].push_back(noww);
				
				//对输出排序 
				for(int j = 0;j < topp;j++){
					sortt[j] = f[cnt][j];
				}
				sort(sortt ,sortt + topp);
				for(int j = 0;j < topp;j++){
					f[cnt][j] = sortt[j];
				}
	
			}
		}else if(ins[son] == 1){
			low[noww] = min(low[noww],low[son]);
		}
	}
}


int main(){
	cin>>n>>m;

	int u,v;
	for(int i = 1;i <= m;i++){
		cin>>u>>v;
		if(u == v){
			continue;
		}
		add(u,v);
		add(v,u); 
	}
	
	for(int i = 1;i <= n;i++){
		if(dfn[i] == 0){//若未被访问过 
			root = i;//以当前节点为树根进行dfs 
			tarjan(i);
		}
	}
	
	cout<<cnt<<endl;
	for(int i = 1;i <= cnt;i++){
		cout<<f[i].size()<<" ";
		for(int j = 0;j < f[i].size();j++){
			cout<<f[i][j]<<" ";
		}
		cout<<endl;
	}  
	
	
	
	return 0;
}


2024/10/23 11:11
加载中...