单位网站建设实施方案,做微商做什么网站比较好,临淄关键词网站优化哪家好,一个简单的网站搭建教程题目描述 X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包#xff0c;为了安全起见#xff0c;必须恰好被转发两次到达目的地。该包可能在任意一个节点产生#xff0c;我们需要知道该网络中一共有多少种不同的转发路径。 源地址和目标地址…题目描述 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
注意 return位置不要放错不然dfs回不来可就糟糕了写题时很容易犯这个错。
代码如下
#include iostream
#include vector
using namespace std;
const int N 1e5 10;vectorintg[N];
int d[10];
int ans;
void dfs(int u, int s) {if (s 4) {if (d[2] ! d[0] d[3] ! d[1]) {ans;//return (1)}return ;//这个return不要写到(1)的位置不然dfs不会回头了。}for (int i 0; i g[u].size(); i) {d[s] g[u][i];dfs(g[u][i], s 1);}
}int main() {int n, m;cin n m;for (int i 1; i m; i) {int a, b;cin a b;g[a].push_back(b);g[b].push_back(a);}for (int i 1; i n; i) {d[0] i;dfs(i, 1);}cout ans endl;return 0;
}
