如果用邻接矩阵存储,边的数组要开多大呀
查看原帖
如果用邻接矩阵存储,边的数组要开多大呀
647347
yushen6474楼主2024/3/28 17:49

我看题目边数是10510^5,为什么我用10510^5就错了

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

const int N=1010,M=110000;

int n,m;
int Enums[N];
int Head[N],Elem[M],Next[M];
bool G[N][N];
int Index;

void add(int a,int b){
	Elem[Index]=b;
	Next[Index]=Head[a];
	Head[a]=Index++;
}

int main(){

	memset(Head,-1,sizeof(Head));
	cin>>n>>m;	
	while(m--){
		int a,b;
		cin>>a>>b;
		G[a][b]=true;
		G[b][a]=true;
		Enums[a]++;
		Enums[b]++;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<G[i][j]<<" ";
			
		}cout<<endl;
		
		
		for(int j=n;j>=1;j--){
			if(G[i][j]){
				add(i,j);
			}
		}
	}

	for(int i=1;i<=n;i++){
		cout<<Enums[i]<<" ";
		
		for(int j=Head[i];j!=-1;j=Next[j]){
			cout<<Elem[j]<<" ";
		}
		
		cout<<endl;
	}
	return 0;
}
2024/3/28 17:49
加载中...