蓝桥杯历届试题-网络寻路 （C++代码）-------momoc

解题思路:

我直接用数组模拟邻接表。

没有用vector 向量 ，如果开N*N的数组，内存肯定爆炸。

用vector可以优化一下内存。

注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;
#define N 10001
typedef long long ll;
int n,m;
vector<int> p[N];
int son[N][N/10];//存储儿子所在位置 
int sonCount[N]={0};//儿子的个数 
int st =  0;//保存当前开始的节点
bool vis[N] = {0};
ll ans =0;
void dfs(int x,int Count){
	if(Count>=4){
		ans ++;
		return ;
	}
	
	for(int i=0;i<sonCount[x];i++){
		
		if(vis[son[x][i]] == 0 || (son[x][i]==st && Count==3 &&vis[son[x][i]] == 1 )){
			//cout<<"Count = "<<Count<<" son = "<<son[x][i]<<endl;
			vis[son[x][i]] = 1;
			dfs(son[x][i],Count + 1);
			if(son[x][i]!=st) //不能对开始点重新赋值 自己可以想一下  我卡这里很久了 
				vis[son[x][i]] = 0;
		}		
	}	
}
int main (){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		
		son[x][sonCount[x]] = y;
		sonCount[x]++;	
		
		son[y][sonCount[y]] = x;
		sonCount[y]++;
	}
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof vis);
		st =  i;
		vis[i] = 1;
		dfs(i,1);
	}
	printf("%lld",ans);
	return 0;
}

附：使用 vector数组版 

#include <bits/stdc++.h>
using namespace std;
#define N 10001
typedef long long ll;
int n,m;
vector<int> p[N];
int st =  0;
bool vis[N] = {0};
ll ans =0;
void dfs(int x,int Count){
	if(Count>=4){
		ans ++;
		return ;
	}
	for(int i=0;i<p[x].size();i++){		
		if(vis[p[x][i]] == 0 || (p[x][i]==st && Count==3 )){
			vis[p[x][i]] = 1;
			dfs(p[x][i],Count + 1);
			if(p[x][i]!=st) //不能对开始点重新赋值 
				vis[p[x][i]] = 0;
		}		
	}	
}
int main (){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		p[x].push_back(y);
		p[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		memset(vis,0,sizeof vis);
		st =  i;
		vis[i] = 1;
		dfs(i,1);
	}
	printf("%lld",ans);
	return 0;
}