侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【DFS】网络寻路【蓝桥杯】

GabrielxD
2023-04-24 / 0 评论 / 0 点赞 / 147 阅读 / 962 字
温馨提示:
本文最后更新于 2023-04-24,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

网络寻路 - 蓝桥云课


题目描述

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

源地址和目标地址可以相同,但中间节点必须不同。

如下图所示的网络。

图片描述

1 -> 2 -> 3 -> 1 是允许的; 1 -> 2 -> 1-> 2 或者 1->2->3->2 都是非法的。

输入描述

输入数据的第一行为两个整数 N,MN, M ,分别表示节点个数和连接线路的条数 (1N104,0M105)(1 \leq N \leq 10^4, 0 \leq M \leq 10^5)

接下去有 MM 行,每行为两个整数 uuvv ,表示节点 uuvv 联通 (1u,vN,u!=v)(1 \leq u,v \leq N , u!=v)

输入数据保证任意两点最多只有一条边连接,并且没有自己连自己的边,即不存在重边和自环。

输出描述

输出一个整数,表示满足要求的路径条数。

输入输出样例

示例

输入

3 3
1 2
2 3
1 3

输出

6

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

解题

方法一:DFS

思路

1n1\dots n 每个点为起点尝试进行 DFS ,找到共走 44 个节点且不经过重复节点(终点可以与起点重复)的合法路径即可增加答案。

dfs(u,cnt,src)dfs(u, cnt, src)uu 表示当前节点, cntcnt 表示当前路径经过了多少个点, srcsrc 表示当前路径的起点 ):

  • 出口:当 cnt=4cnt = 4 时,说明当前路径是经过了 44 个点的合法路径,增加答案,退出递归;
  • 枚举与点 uu 相连的顶点 vv 尝试作为路径上的第 cnt+1cnt + 1 个顶点:
    • 如果当前不是在枚举终点( cnt3cnt \neq 3 )且枚举到了起点( v=srcv = src ),说明该顶点不能作路径上的第 cnt+1cnt + 1 个点,跳过本次迭代;
    • 如果没有枚举到路径上已有到点( vis[v]=falsevis[v] = false ),或是当前在枚举终点且枚举到了起点( cnt=3,v=srccnt = 3, v = src ),尝试把 vv 作为路径上的第 cnt+1cnt + 1 个点( vis[v]=truevis[v] = true ),递归下一个点: dfs(v,cnt+1,src)dfs(v, cnt + 1, src)
      • 回溯( vis[v]=falsevis[v] = false )。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static int[] h, e, ne;
    static int idx;
    static boolean[] vis;
    static int ans;

    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static void dfs(int u, int cnt, int src) {
        if (cnt == 4) {
            ++ans;
            return;
        }
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (cnt != 3 && v == src) continue;
            if (!vis[v] || (cnt == 3 && v == src)) {
                vis[v] = true;
                dfs(v, cnt + 1, src);
                vis[v] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); n = (int) in.nval;
        in.nextToken(); m = (int) in.nval;
        h = new int[n + 1];
        Arrays.fill(h, -1);
        e = new int[m * 2];
        ne = new int[m * 2];
        while (m-- > 0) {
            in.nextToken(); int u = (int) in.nval;
            in.nextToken(); int v = (int) in.nval;
            add(u, v); add(v, u);
        }
        vis = new boolean[n + 1];
        for (int u = 1; u <= n; ++u) dfs(u, 1, u);
        System.out.println(ans);
    }
}
0

评论区