历届试题 网络寻路
程序员文章站
2022-06-11 10:32:57
...
@ 蓝桥杯 练习系统 历届试题 PREV-13
资源限制
时间限制:1.0s 内存限制:256.0MB
问题描述
问题描述
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)。
输入数据保证任意两点最多只有一条边连接,并且没有自己连自己的边,即不存在重边和自环。
输出格式
输出一个整数,表示满足要求的路径条数。
测试样例1
in:
3 3
1 2
2 3
1 3
out:
6
测试样例2
in:
4 4
1 2
2 3
3 1
1 4
out:
10
AC code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static boolean[] marked;
static List<Integer>[] graph;
public static void main(String[] args) throws IOException {
InputReader in = new InputReader(System.in, " ");
int n = in.nextInt() + 1, m = in.nextInt(), cnt = 0, x, y;
marked = new boolean[n];
graph = new List[n];
for (int i = 1; i < n; i++)
graph[i] = new ArrayList();
while (m-- > 0) {
x = in.nextInt();
y = in.nextInt();
graph[x].add(y);
graph[y].add(x);
}
for (int i = 1; i < n; i++) cnt += dfs(i, 1);
System.out.print(cnt);
}
static int dfs(int i, int d) {
if (d == 3) return graph[i].size() - 1;
int res = 0;
marked[i] = true;
for (int v: graph[i]) {
if (marked[v]) continue;
res += dfs(v, d + 1);
}
marked[i] = false;
return res;
}
static class InputReader {
BufferedReader read;
StringTokenizer tok;
String delimiters;
InputReader(InputStream in) { this(in, " \n\t\r\f"); }
InputReader(InputStream in, String delimiters) {
this.read = new BufferedReader(new InputStreamReader(in));
this.tok = new StringTokenizer("", this.delimiters = delimiters);
}
String next() {
while (!tok.hasMoreTokens())
try {
tok = new StringTokenizer(read.readLine(), delimiters);
} catch (IOException e) { }
return tok.nextToken();
}
int nextInt() { return Integer.parseInt(next()); }
}
}
愣了一下,然后发现上道题改改就能用
题目说的拐弯抹角的
翻译过来就是找到所有长度为 4 的路径,起始节点可以和结束节点重复
所以没有必要做任何特殊判断,搜索最大深度为 4 搜到底就返回当前结点度 - 1(减去来路)
上一篇: PHP会话控制
下一篇: 蓝桥杯 C语言 试题 历届试题 网络寻路