求助,悬关
查看原帖
求助,悬关
848391
fantastic_dream楼主2023/4/29 14:55

以下是求无向图的连通分量

蒟蒻真不知道有什么问题哇

#include<bits/stdc++.h>
using namespace std;
const int MA=1000010;
int n,e,cnt=0,head[MA],ans=0;
bool vi[MA];
struct Edge{
	int e,ne;
}edge[MA],t;
queue<int> p;
void add(int u,int v){
    edge[cnt].e=v;
    edge[cnt].ne=head[u];
    head[u]=cnt++;
}
void bfs(int x){
	while(!p.empty()){
		int a=p.front();
		vi[a]=true;
		p.pop();
		for(int j=head[a];~j;j=edge[j].ne){
			if(!vi[edge[j].e])
				p.push(edge[j].e);		
		}		
	}
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>e;
	int u,v;
	for(int i=1;i<=e;i++){
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!vi[i]){
			p.push(i);
			ans++;
			bfs(i);	
		}
	}
	cout<<ans;
}

边数可能拉到10^8条,帮忙看下有什么问题,蟹蟹咯

2023/4/29 14:55
加载中...