蓝桥杯历届试题网络寻路（java）

痛定思痛。 2022-03-25 08:57 217阅读 0赞

问题描述

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

3 3

1 2

2 3

1 3

样例输出1

样例输入2

4 4

1 2

2 3

3 1

1 4

样例输出2

--------------------

## 分析 ##

太郁闷了居然超时了，都怪我学艺不精QAQ但我参考了几个网友写的版本感觉我这个是比较好看懂的吧（我不会C++）感觉要想不超时应该要用buffer吧，但是实在不会了，魔鬼一样的测试数据，混个60分QAQ第一次用dfs

import java.util.Scanner;
    public class Main {
        static int m=0;
        static int n;
        static int n1[][];
        public static void main(String[] args) {
            int sum=0;
            Scanner sc = new Scanner(System.in);
            n=sc.nextInt();
            int m=sc.nextInt();
            n1=new int[n+1][n+1];
            for(int i=1;i<n+1;i++) {
                for(int i2=1;i2<n+1;i2++) {
                    n1[i][i2]=0;
                }
            }
            for(int i=1;i<=m;i++) {//有路为1
                int a1=sc.nextInt();
                int a2=sc.nextInt();
                n1[a1][a2]=1;
                n1[a2][a1]=1;
            }
            for(int i=1;i<n+1;i++) {
                sum=search(i,0);
            }
            System.out.println(sum);
        }
    
        static int search(int i,int count) {
            if(count==3)
                m+=1;
            else {
                    for(int i2=1;i2<n+1;i2++) {
                        if(n1[i][i2]==1){
                            n1[i][i2]=0;
                            n1[i2][i]=0;
                            search(i2,count+1);
                            n1[i][i2]=1;
                            n1[i2][i]=1;
                        }
                    }
                }
            return m;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDA5MTg5MA_size_16_color_FFFFFF_t_70]: /images/20220325/6b4eea5cb09d41dca40061637c044a86.png