代码随想三刷图论篇1

• 98. 所有可达路径
• • 题目
  • 代码
• 99. 岛屿数量
• • 题目
  • 代码
• 100. 岛屿的最大面积
• • 题目
  • 代码
• 101. 孤岛的总面积
• • 题目
  • 代码
• 102. 沉没孤岛
• • 题目
  • 代码
• 103. 水流问题
• • 题目
  • 代码

98. 所有可达路径

题目

链接

代码

import java.util.*;  class Main{     public static void main(String [] args){         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();//节点         int M = sc.nextInt();//边数         int[][] pic = new int[N+1][N+1];//0不用         for(int i =0;i             pic[sc.nextInt()][sc.nextInt()] = 1;         }         used = new boolean[N+1];         for(int i = 1;i<=1;i++){             paths.add(i);             dfs(pic,i,N);             paths.remove(paths.size()-1);         }         for(int i =0;i             for(int j =0;j                 System.out.print(result.get(i).get(j));                 if(j                     System.out.print(" ");                 }             }             System.out.println();         }         if(result.size()<=0){             System.out.println(-1);         }              }     static List>  result = new ArrayList();     static List  paths = new ArrayList();     static boolean[] used;     public static void dfs(int[][] pic,int node,int N){         if(paths.get(paths.size()-1)==N){             result.add(0,new ArrayList(paths));             return;         }         for(int j =1;j             if(!used[j]&&pic[node][j]==1){                 used[j] = true;                 paths.add(j);                 dfs(pic,j,N);                 paths.remove(paths.size()-1);                 used[j] = false;             }         }              } } 

99. 岛屿数量

题目

链接

代码

import java.util.*; class Main{               public static void main(String[] args){         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int M = sc.nextInt();         int[][] pic = new int[N][M];         for(int i =0;i             for(int j =0;j                 pic[i][j] = sc.nextInt();             }         }         for(int i =0;i             for(int j =0;j                 if(pic[i][j]==1){                     count++;                     dfs(pic,i,j);                 }             }         }         System.out.println(count);     }     static int count = 0;     public static void dfs(int[][] pic,int i,int j){         pic[i][j] = 0;         if(i>=1&&pic[i-1][j]==1){             dfs(pic,i-1,j);         }         if(j>=1&&pic[i][j-1]==1){             dfs(pic,i,j-1);         }         if(i             dfs(pic,i+1,j);         }         if(j             dfs(pic,i,j+1);         }     } } 

100. 岛屿的最大面积

题目

链接

代码

import java.util.*; class Main{               public static void main(String[] args){         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int M = sc.nextInt();         int[][] pic = new int[N][M];         for(int i =0;i             for(int j =0;j                 pic[i][j] = sc.nextInt();             }         }         int maxCount = 0;         for(int i =0;i             for(int j =0;j                 if(pic[i][j]==1){                     count=0;                     dfs(pic,i,j);                     maxCount = Math.max(maxCount,count);                     }             }         }         System.out.println(maxCount);     }     static int count = 0;     public static void dfs(int[][] pic,int i,int j){         pic[i][j] = 0;         count++;         if(i>=1&&pic[i-1][j]==1){             dfs(pic,i-1,j);         }         if(j>=1&&pic[i][j-1]==1){             dfs(pic,i,j-1);         }         if(i             dfs(pic,i+1,j);         }         if(j             dfs(pic,i,j+1);         }     } } 

101. 孤岛的总面积

题目

链接

代码

import java.util.*; class Main{               public static void main(String[] args){         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int M = sc.nextInt();         int[][] pic = new int[N][M];         for(int i =0;i             for(int j =0;j                 pic[i][j] = sc.nextInt();             }         }         int maxCount = 0;         for(int i =0;i             for(int j =0;j                 if(pic[i][j]==1){                     count=0;                     isL = true;                     dfs(pic,i,j);                     if(isL){                         maxCount += count;                         }                 }             }         }         System.out.println(maxCount);     }     static int count = 0;     static boolean isL = true;     public static void dfs(int[][] pic,int i,int j){         if(i==0||j==0||i==pic.length-1||j==pic[0].length-1){             isL = false;         }         pic[i][j] = 0;         count++;         if(i>=1&&pic[i-1][j]==1){             dfs(pic,i-1,j);         }         if(j>=1&&pic[i][j-1]==1){             dfs(pic,i,j-1);         }         if(i             dfs(pic,i+1,j);         }         if(j             dfs(pic,i,j+1);         }     } } 

102. 沉没孤岛

题目

链接

代码

import java.util.*; class Main{               public static void main(String[] args){         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int M = sc.nextInt();         int[][] pic = new int[N][M];         for(int i =0;i             for(int j =0;j                 pic[i][j] = sc.nextInt();             }         }         for(int i =0;i             for(int j =0;j                 if(pic[i][j]==1){                     count=0;                     isL = true;                     list.clear();                     dfs(pic,i,j);                     if(!isL){                         for(int k = 0;k                             int [] temp = list.get(k);                             pic[temp[0]][temp[1]] = 1;                         }                     }                 }             }         }                  for(int i =0;i             for(int j =0;j                              System.out.print(pic[i][j]+" ");             }             System.out.println();         }     }     static int count = 0;     static List list = new ArrayList();     static boolean isL = true;     public static void dfs(int[][] pic,int i,int j){         if(i==0||j==0||i==pic.length-1||j==pic[0].length-1){             isL = false;         }         list.add(new int[]{i,j});         pic[i][j] = 0;         count++;         if(i>=1&&pic[i-1][j]==1){             dfs(pic,i-1,j);         }         if(j>=1&&pic[i][j-1]==1){             dfs(pic,i,j-1);         }         if(i             dfs(pic,i+1,j);         }         if(j             dfs(pic,i,j+1);         }     } } 

103. 水流问题

题目

链接

代码

import java.util.*; class Main{               public static void main(String[] args){         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int M = sc.nextInt();         int[][] pic = new int[N][M];         for(int i =0;i             for(int j =0;j                 pic[i][j] = sc.nextInt();             }         }                  used1 = new boolean[N][M];         used2 = new boolean[N][M];         for(int j = 0;j             dfs(pic,0,j,false);             dfs(pic,N-1,j,true);         }         for(int i = 0;i             dfs(pic,i,0,false);             dfs(pic,i,M-1,true);         }                           for(int i =0;i             for(int j =0;j                 if(used1[i][j]&&used2[i][j]){                     System.out.println(i+" "+j);                    }             }          }              }     static boolean[][] used1; //是否访问过     static boolean[][] used2; //是否访问过     //暂存一回合可到达的坐标     static List list = new ArrayList();     //是否到边     public static void dfs(int[][] pic,int i,int j,boolean flag){         if(flag){             if(used1[i][j]){                 return;             }             used1[i][j] = true;         }else{             if(used2[i][j]){                 return;             }             used2[i][j] = true;         }                  if(i>=1&&pic[i-1][j]>=pic[i][j]){             dfs(pic,i-1,j,flag);         }         if(j>=1&&pic[i][j-1]>=pic[i][j]){             dfs(pic,i,j-1,flag);         }         if(i=pic[i][j]){             dfs(pic,i+1,j,flag);         }         if(j=pic[i][j]){             dfs(pic,i,j+1,flag);         }              } }