zjh

用户名：speaksoftly

访问量：24719

签　名：

搞spring去了...不能愉快的刷题了...

等　　级
排　　名	172
经　　验	6956
参赛次数	10
文章发表	37
年　　龄	0
在职情况	学生
学　　校	海南
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-数的划分-题解(C++代码)蒟蒻的me也来写一写题解
浏览：949

蓝桥杯历届试题-国王的烦恼（C++代码）并查集&生成树
浏览：877

蓝桥杯历届试题-城市建设（C++代码）并查集&最小生成树kruskal
浏览：1227

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

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

　　作者: zjh　　　　发表时间：2019-07-15 18:21:39 浏览：587　|　评论：0　

原题链接：蓝桥杯历届试题-网络寻路

```cpp

题目大致意思是说你要找到从任意一点开始，经过3个结点的方案数
并且除了起点和终点外(终点可以是开始点，也可以是其他未访问过的点)，其他点只能访问一次
例如：
1->2->3->1
1->2->3->4
1->3->2->1
都是正确的路径
1->2->3->2
1->2->4->2
2->1->2->3
都是错误的路径

并且，根据样例分析
1->2->3->4 和 4->3->2->1是两条不同的路径，所以顺序不同也是两条不同的路径

ps : 说是难题，实际上是个大水题 (逃

#include "iostream"
#include "cstdio"
#include "cstdlib"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "vector"
#include "stack"
#include "map"
#include "set"

using namespace std;

typedef long long ll;
const int INF = 1e9;
const int maxn = 10010;

int n, m;
vector<int> G[maxn];	//用邻接表，用邻接矩阵会内存超限
bool vis[maxn];		 //判重
ll res = 0;			 //结果计数

/**
 * v : 当前访问的结点
 * k : 转发次数
 * root : 最开始的根结点
 */
void dfs(int v, int k, int root) {
	if(k == 2) {	//转发次数刚好 2 次
		//枚举该点所有连接的，并且没走过的结点，包括根结点，只要存在就计数
		for(int i = 0; i < G[v].size(); ++i) {
			if(!vis[G[v][i]] || G[v][i] == root) {
				res++;
			}
		}
		return ;
	}
	//枚举该点的所有边，没走过的都去走一遍
	for(int i = 0; i < G[v].size(); ++i) {
		if(!vis[G[v][i]]) {
			vis[G[v][i]] = true;
			dfs(G[v][i], k + 1, root);
			vis[G[v][i]] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	for(int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}

//每个点都作为起始点出发搜索
	for(int i = 1; i <= n; ++i) {
		memset(vis, false, sizeof vis);
		vis[i] = true;
		dfs(i, 0, i);
	}
	cout << res << endl;
	return 0;
}
```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zjh

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

C二级辅导-阶乘数列（C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

人见人爱A+B （C语言代码）

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

评论区

精彩推荐

回文数(一) （C语言代码）

wu-淘淘的名单（C++代码）

WU-拆分位数（C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

1025题解

A+B for Input-Output Practice (V) （C语言代码）

星期判断机（C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

zjh

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.4 （Java代码）

C二级辅导-阶乘数列 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

人见人爱A+B （C语言代码）

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

评论区

精彩推荐

回文数(一) （C语言代码）

wu-淘淘的名单 （C++代码）

WU-拆分位数 （C++代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

1025题解

A+B for Input-Output Practice (V) （C语言代码）

星期判断机 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C二级辅导-阶乘数列（C++代码）

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

　　评论区

wu-淘淘的名单（C++代码）

WU-拆分位数（C++代码）

星期判断机（C语言代码）