代码随想三刷图论篇2

• 104. 建造最大岛屿
• • 题目
  • 代码
• 110. 字符串接龙
• • 题目
  • 代码
• 105. 有向图的完全可达性
• • 题目
  • 代码
• 106. 岛屿的周长
• • 题目
  • 代码

104. 建造最大岛屿

题目

链接

代码

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];         used = new boolean[N][M];         for(int i =0;i             for(int j =0;j                 pic[i][j] = sc.nextInt();                 if(pic[i][j]==0){                     used[i][j] = true;                 }             }         }         int maxCount = 0;         int index = 1;         Map map = new HashMap();          for(int i =0;i             for(int j =0;j                 if(pic[i][j]==1){                     list.clear();                     dfs(pic,i,j);                     for(int k = 0;k                         int[] temp= list.get(k);                         pic[temp[0]][temp[1]] = index;                     }                     map.put(index,list.size());                     maxCount = Math.max(maxCount,list.size());                     index++;                 }             }         }         for(int i =0;i             for(int j =0;j                 if(pic[i][j]==0){                     Set sett = new HashSet();                     int count = 1;                     if(i>=1 && !sett.contains(pic[i-1][j])){                         count+=map.getOrDefault(pic[i-1][j],0);                         sett.add(pic[i-1][j]);                     }                     if(j>=1 && !sett.contains(pic[i][j-1])){                         count+=map.getOrDefault(pic[i][j-1],0);                         sett.add(pic[i][j-1]);                     }                     if(i                         count += map.getOrDefault(pic[i+1][j],0);                         sett.add(pic[i+1][j]);                     }                     if(j                         count+=map.getOrDefault(pic[i][j+1],0);                         sett.add(pic[i][j+1]);                     }                     maxCount = Math.max(maxCount,count);                 }             }         }         System.out.println(maxCount);              }     static boolean[][] used;     static List list = new ArrayList();     public static void dfs(int[][] pic,int i,int j){         if(i<0||j<0||i>=pic.length||j>=pic[0].length||used[i][j]){             return;         }         used[i][j] = true;         list.add(new int[]{i,j});         if(i>=1){             dfs(pic,i-1,j);         }         if(j>=1){             dfs(pic,i,j-1);         }         if(i             dfs(pic,i+1,j);         }         if(j             dfs(pic,i,j+1);         }     } } 

110. 字符串接龙

题目

链接

代码

import java.util.*;  class Main{     public static void main(String[] args){         Scanner sc = new Scanner(System.in);                  int N = Integer.valueOf(sc.nextLine());         String beginStr = sc.next();         String endStr = sc.next();         Set strList = new HashSet();         for(int i = 0;i             strList.add(sc.next());         }         int count = 0;         Deque  queue = new LinkedList();         queue.addLast(beginStr);         while(!queue.isEmpty()){             count++;             int size = queue.size();             for(int step = 0;step                 String word = queue.removeFirst();                 for(int i=0;i< word.length();i++){                                      char[] chars = word.toCharArray();                     for(char k = 'a';k<='z';k++){                         chars[i] = k;                            String newWord = String.valueOf(chars);                         if(newWord.equals(endStr)){                             System.out.println(count+1);                             return;                         }                         if(strList.contains(newWord)){                             strList.remove(newWord);                             queue.addLast(newWord);                         }                     }                 }             }         }                  System.out.println(0);     } } 

105. 有向图的完全可达性

题目

链接

代码

import java.util.*;  class Main{          public static void main(String[] args){         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int K = sc.nextInt();         Map> map = new HashMap();         for(int i =1;i<=N;i++){             map.put(i,new HashSet());         }         for(int i = 0;i             int num1 = sc.nextInt();             int num2 = sc.nextInt();             map.get(num1).add(num2);         }         used = new boolean[N+1];         dfs(map,1);         for(int i =1;i<=N;i++){             if(!used[i]){                 System.out.println(-1);                 return;             }         }         System.out.println(1);     }     static boolean[] used;     public static void dfs(Map> map,int key){         if(used[key]){             return;         }         used[key] = true;         Set set =map.get(key);         for(int nextNum:set){             dfs(map,nextNum);         }     } } 

106. 岛屿的周长

题目

链接

代码

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 sum = 0;    // 陆地数量         int cover = 0;  // 相邻数量         for (int i = 0; i < N; i++) {             for (int j = 0; j < M; j++) {                 if (pic[i][j] == 1) {                     sum++; // 统计总的陆地数量                     // 统计上边相邻陆地                     if(i - 1 >= 0 && pic[i - 1][j] == 1) cover++;                     // 统计左边相邻陆地                     if(j - 1 >= 0 && pic[i][j - 1] == 1) cover++;                     // 为什么没统计下边和右边？ 因为避免重复计算                 }             }         }         System.out.println(sum * 4 - cover * 2 );     } }