腾讯秋招web后台方向笔试题第二题，寻找重要城市，dfs解法。_dfs应用-计算可达城市对

如需转载，请注明出处：https://blog.csdn.net/qq_34761108/article/details/82728430

问题描述：

      小Q所在的王国有n个城市，城市之间有m条单向道路连接起来。对于一个城市v，从城市v出发可到达的城市数量为x,从某个城市出发可达到的城市v的城市数量为y,如果y>x，则城市v是一个重要城市(间接可达也算可以到达)。

      小Q希望你能帮他计算一下王国中一共有多少个重要城市。

     输入描述：

             输入包括 m+1行

             第一行包括两个数n和m（1<=n,m<=1000),分别表示城市数和道路数。

             接下来m行，每行两个树u,v（1<=u,v<=n),表示一条从u到v的有向道路输入中可能包含重边和自环

      输出秒速：

             输出一个数，重要城市的个数。

       例子：

         输入：

              4 3

              2 1

              3 2

              4 3

         输出：

               2

        思路：

                  

         如题，城市一可达的城市有0个，可达城市一的城市有3个（城市2，城市3，城市4）

                    城市二可达的城市有1个，可达城市二的城市有2个（城市3，城市4）

                    城市三可达的城市有2个，可达城市三的城市有1个。

                    城市四可达的城市有3个，可达城市四的城市有0个。

                 因此最终的答案是2.

          因此我先维护一个二维的数组，来存储输入的数据:（注意，我这里加入了城市一到城市三的路径）

                      

                        

             X表示不可达，O表示可达。

          根据题意，我们还应该再维护一个可达矩阵，因为题目给出的条件是间接可达也算是可达。

                     

          X表示不可达，O表示可达。           

          有了这个矩阵，我们可以清楚的知道，城市x可到达哪些城市。

             比如我们想知道城市一可达哪些城市，只要看第一行就可知道城市一可达两个城市，分别是城市2和城市3。想知道哪些城市可达城市一，只要看第一列，即城市2，城市3，城市4均可达城市一。

           因此，只要我们能够生成这个数列，就可以解出此题。

           为了够造这个矩阵，我采用的是深度优先算法(dfs)

           具体代码如下：

                  

public class Main9 {
 
 
    public static void main(String[] args){
/**
        Scanner scanner=new Scanner(System.in);
        String a=scanner.nextLine();
        String[] strings=a.split(" ");
        int k1=Integer.valueOf(strings[0]);
        int k2=Integer.valueOf(strings[1]);
        int[][] kk=new int[k1+1][k1+1];
        for(int i=0;i<k2;i++){
            String a2=scanner.nextLine();
            String[] strings1=a2.split(" ");
            int n1=Integer.valueOf(strings1[0]);
            int n2=Integer.valueOf(strings1[1]);
            kk[n1][n2]=1;
        }
**/
        int[][] kk=new int[5][5];
        kk[1][3]=1;
        kk[2][1]=1;
        kk[3][2]=1;
        kk[4][3]=1;            //题目给出的数据
 
        int[][] reachable=new int[5][5];    //可达性矩阵
 
        for(int i=1;i<5;i++){              //通过循环，dfs构造每一行数据
            dfs(reachable,kk,i,i);
        }
 
 
        for(int i=1;i<reachable.length;i++){     //打印可达性矩阵
            for(int j=1;j<reachable.length;j++){
                System.out.print(reachable[i][j]);
            }
            System.out.println();
        }
 
        int count =0;
        for(int i=1;i<kk.length;i++){            //计算重要城市的个数
            int out=0;
            for(int d=1;d<kk.length;d++){
                if(reachable[i][d]==1){
                    out++;
                }
            }
 
            int in=0;
            for(int j=1;j<kk.length;j++){
                if(reachable[j][i]==1){
                    in++;
                }
            }
            if(in>out){
                count++;
            }
        }
        System.out.println(count);
 
    }
 
    /**
     *
     * @param reachable 可达性矩阵
     * @param kk        题目的原始数据
     * @param now       当前行
     * @param x         当前列
     */
    public static void dfs(int[][] reachable,int[][] kk,int now,int x){
 
        for(int i=1;i<reachable.length;i++){  //dfs搜索
            if(kk[x][i]==1&&
                        now!=i&&
                            reachable[now][i]!=1){ 
                reachable[now][i]=1;
                    dfs(reachable,kk,now,i); //递归
            }
        }
 
    }
}

如有疑问，欢迎留言~