ISSAC

用户名：uq_50089742160

访问量：5766

签　名：

等　　级
排　　名	705
经　　验	3912
参赛次数	8
文章发表	8
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯历届试题-网络寻路-题解（C++代码）
浏览：377

信息学奥赛一本通T1311-求逆序对-题解（C++代码）
浏览：2067

你可能喜欢

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

C语言训练-求1+2!+3!+...+N!的和（C++代码）

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

　　作者: ISSAC　　　　发表时间：2020-05-26 13:19:57 浏览：377　|　评论：0　

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

题目 1452: [蓝桥杯][历届试题]网络寻路

时间限制: 1Sec 内存限制: 128MB 提交: 308 解决: 129

题目描述
X  国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。
源地址和目标地址可以相同，但中间节点必须不同。
如下图所示的网络。

1  ->   2  ->   3  ->   1  是允许的
1  ->   2  ->   1  ->   2  或者  1  ->   2  ->   3  ->   2  都是非法的。
输入
输入数据的第一行为两个整数N  M，分别表示节点个数和连接线路的条数(1< =N< =10000;  0< =M< =100000)。 
接下去有M行，每行为两个整数  u  和  v，表示节点u  和  v  联通(1< =u,v< =N  ,  u!=v)。 
输入数据保证任意两点最多只有一条边连接，并且没有自己连自己的边，即不存在重边和自环。 
输出
输出一个整数，表示满足要求的路径条数。
样例输入
4 4
1 2
2 3
3 1
1 4
样例输出
10

```cpp
//网络寻路！大数节点图，临界矩阵不行
//只能采取邻接表，这里采用 链式向前星 和 dfs来尝试解决此题 
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
struct node{
	int u;
	int v;
	int front;
}edge[200005];
bool vis[10005];
int head[10005];
int cnt = 0;
long long sum =0;
void add(int u,int v)
{
	edge[cnt].u = u;
	edge[cnt].v = v;
	edge[cnt].front = head[u];
	head [u] = cnt++;
	
	edge[cnt].u = v;
	edge[cnt].v = u;
	edge[cnt].front = head[v];
	head [v] = cnt++;
}

void dfs(int u,int v,int step)
{   
	if(step==2)
	{
		for(int i =head[v];i!=-1;i=edge[i].front)
			if(vis[edge[i].v]==false||edge[i].v==u) sum++;
			
		return ;
	}
	for(int i =head[v];i!=-1;i=edge[i].front)
	{
		if(vis[edge[i].v]==false)
		{   
			vis[v] =true;
			dfs(u,edge[i].v,step+1);
			vis[v] =false;
		}
	}
	return ;
}
int main()
{
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	memset(vis,false,sizeof(vis));
	for(int i =0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	
	for(int i = 1;i<=n;i++)
	{
		vis[i] = true;
		dfs(i,i,0);	
	}
	cout<<sum<<endl;
}
```

0.0分

1 人评分

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

ISSAC

TA的其他文章

你可能喜欢

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

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

一个简单易懂的代码

小九九（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

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

评论区

精彩推荐

母牛的故事（C语言代码）

2^k进制数（C++代码）使用递归方法

C二级辅导-同因查找（C语言代码）

矩形面积交（Java代码）

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

字符串对比（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

交换Easy （C语言代码）

找出最长的字符串来（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）

ISSAC

TA的其他文章

你可能喜欢

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

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

一个简单易懂的代码

小九九 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和 （C++代码）

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

评论区

精彩推荐

母牛的故事 （C语言代码）

2^k进制数 （C++代码）使用递归方法

C二级辅导-同因查找 （C语言代码）

矩形面积交 （Java代码）

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

字符串对比 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

交换Easy （C语言代码）

找出最长的字符串来 （C语言代码）

青年歌手大奖赛_评委会打分 （C语言代码）

小九九（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C++代码）

　　评论区

母牛的故事（C语言代码）

2^k进制数（C++代码）使用递归方法

C二级辅导-同因查找（C语言代码）

矩形面积交（Java代码）

字符串对比（C语言代码）

找出最长的字符串来（C语言代码）

青年歌手大奖赛_评委会打分（C语言代码）