devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

79-89_arrays.stream(in.nextline().split(",")).maptoint(i

作者：Cpp五条 | 2024-02-21 00:14:57

赞

踩

arrays.stream(in.nextline().split(",")).maptoint(integer::parseint).toarray(

【不爱施肥的小布】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4. import java.math.BigInteger;
  5. import java.util.stream.Stream;
  6.  
  7. class Main {
  8.     public static void main(String[] args) {
  9.         // 处理输入
  10.         Scanner in = new Scanner(System.in);
  11.  
  12.         int m = in.nextInt();
  13.         int n = in.nextInt();
  14.         in.nextLine();
  15.         Integer[] fields = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
  16.  
  17.         // 最少天数小于果林大小可直接返回-1
  18.         if (n<m) {
  19.             System.out.println(-1);
  20.             return;
  21.         }
  22.         // 最少天数等于果林大小可直接返回max(fields)
  23.         if (n==m) {
  24.             System.out.println((int) Collections.max(Arrays.asList(fields)));
  25.             return;
  26.         }
  27.  
  28.         //排序找到最大最小值
  29.         Arrays.sort(fields);
  30.         int left = 0; 
  31.         int right = fields[fields.length - 1]; 
  32.     
  33.         int result = -1;
  34.     
  35.         while (left +1 < right) {
  36.             //取中间位置的值作为效能k，这里的k取得是其在数组中的index
  37.             int k = (int) Math.ceil((double)(left + right) / 2);
  38.  
  39.             int res = cal(k, fields);
  40.  
  41.             if (res - n > 0) {
  42.                 left = k;
  43.             } else {
  44.                 result = k;
  45.                 right = k; 
  46.             }
  47.         }
  48.         System.out.println(result);
  49.     }
  50.  
  51.     //判断效能为k时，所需总天数
  52.     public static int cal(int k, Integer[] fields) {
  53.         int days = 0;
  54.         for (int i=0;i<fields.length;i++) {
  55.             days += Math.ceil(fields[i] / (double)k);
  56.         }
  57.         return days;
  58.     }
  59.  
  60. }

【组装新的数组】-200

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4. import java.math.BigInteger;
  5. import java.util.stream.Stream;
  6.  
  7. class Main {
  8.     public static int m;
  9.     public static int min_num;
  10.     public static void main(String[] args) {
  11.         // 处理输入
  12.         Scanner in = new Scanner(System.in);
  13.         Integer[] nums = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
  14.         m = in.nextInt();
  15.  
  16.         //排序找到最小值
  17.         Arrays.sort(nums);
  18.         min_num = nums[0];
  19.  
  20.         System.out.println(dfs(nums, 0, 0, 0));
  21.     }
  22.  
  23.     public static int dfs(Integer[] nums, int index, int sum, int count) {
  24.         if (sum > m) {
  25.             return count;
  26.         }
  27.  
  28.         //满足边界条件+1
  29.         if (sum <= m && m - min_num < sum) {
  30.             return count + 1;
  31.         }
  32.     
  33.         for (int i = index; i < nums.length; i++) {
  34.             count = dfs(nums, i, sum + nums[i], count);
  35.         }
  36.     
  37.         return count;
  38.     }
  39.  
  40. }

【快速开租建站】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4. import java.math.BigInteger;
  5. import java.util.stream.Stream;
  6.  
  7. class Main {
  8.     public static void main(String[] args) {
  9.         // 处理输入
  10.         Scanner in = new Scanner(System.in);
  11.         int taskNum = in.nextInt();
  12.         int relationsNum = in.nextInt();
  13.     
  14.         int[][] relation_ids = new int[relationsNum][2];
  15.         for (int i = 0; i < relationsNum; i++) {
  16.             relation_ids[i][0] = in.nextInt();
  17.             relation_ids[i][1] = in.nextInt();
  18.         }
  19.  
  20.         // 每个任务的前置依赖任务个数，也就是拓扑排序中的入度
  21.         int[] upstream = new int[taskNum];
  22.         // 每个任务的下游任务， 也就是拓扑排序中的出度
  23.         List<List<Integer>> downstream =new ArrayList<List<Integer>>(taskNum);
  24.         for (int i=0;i<taskNum;i++) {
  25.             downstream.add(new ArrayList<>());
  26.         }
  27.  
  28.         //初始化入度、出度
  29.         for (int[] relation_id : relation_ids) {
  30.             downstream.get(relation_id[0]).add(relation_id[1]); 
  31.             upstream[relation_id[1]]+=1; 
  32.         }
  33.  
  34.         //队列中保存当前入度为0 的任务id
  35.         LinkedList<Integer[]> queue = new LinkedList<>();
  36.         int result = 1;
  37.     
  38.         for (int i = 0; i < taskNum; i++) {
  39.             //将所有入度为零的任务入队, 默认耗时为1
  40.             if (upstream[i] == 0) {
  41.                 queue.add(new Integer[] {i, result}); 
  42.             }
  43.         }
  44.     
  45.         while (queue.size() > 0) {
  46.             Integer[] current_task = queue.removeFirst();
  47.             int task = current_task[0];
  48.             int time = current_task[1];
  49.         
  50.             for (Integer downstream_task : downstream.get(task)) {
  51.                 // 当前任务的入度减小到0时，放入queue中
  52.                 if (--upstream[downstream_task] == 0) {
  53.                     result = time + 1;
  54.                     queue.add(new Integer[] {downstream_task, result});
  55.                 }
  56.             }
  57.             
  58.         }
  59.     
  60.         System.out.println(result);
  61.  
  62.     }
  63.  
  64. }

【统计友好度最大值】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4. import java.math.BigInteger;
  5. import java.util.stream.Stream;
  6.  
  7. class Main {
  8.     public static void main(String[] args) {
  9.         // 处理输入
  10.         Scanner in = new Scanner(System.in);
  11.         Integer[] seats = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
  12.  
  13.         ArrayList<Integer> left_result_arr = new ArrayList<Integer>();
  14.         Integer left_result = 0;
  15.         for (int i = 0; i < seats.length; i++) {
  16.             if (seats[i] == 0) {
  17.                 left_result_arr.add(left_result);
  18.                 left_result = 0;
  19.             } else if (seats[i] == 1) {
  20.                 left_result +=1;
  21.             } else {
  22.                 left_result =0;
  23.             }
  24.         }
  25.  
  26.         ArrayList<Integer> right_result_arr = new ArrayList<Integer>();
  27.         Integer right_result = 0;
  28.         for (int i = seats.length - 1; i >= 0; i--) {
  29.             if (seats[i] == 0) {
  30.                 right_result_arr.add(right_result);
  31.                 right_result = 0;
  32.             } else if (seats[i] == 1) {
  33.                 right_result +=1;
  34.             } else {
  35.                 right_result =0;
  36.             }
  37.         }
  38.         
  39.         int result = 0;
  40.         for (int i = 0; i < left_result_arr.size(); i++) {
  41.             result = Math.max(result, left_result_arr.get(i) + right_result_arr.get(left_result_arr.size()-i-1));
  42.         }
  43.         System.out.println(result);
  44.     }
  45.  
  46. }

【荒地建设电站 / 区域发电量统计】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4.  
  5. public class Main { 
  6.     public static void main(String[] args) {
  7.         //处理输入
  8.         Scanner in=new Scanner(System.in); 
  9.         List<Integer> params =Arrays.stream(in.nextLine().split(" "))
  10.                 .map(Integer::parseInt)
  11.                 .collect(Collectors.toList());
  12.         int n = params.get(0);
  13.         int m = params.get(1);
  14.         int c = params.get(2);
  15.         int k = params.get(3);
  16.  
  17.         int[][] matrix = new int [n][m];
  18.         for (int i=0;i<n;i++) {
  19.             String[] num_strs =in.nextLine().split(" ");
  20.             for (int j=0;j<m;j++) {
  21.                 matrix[i][j] = Integer.parseInt(num_strs[j]);
  22.             }  
  23.         }
  24.  
  25.         System.out.println(get_area_count(matrix, k, c));
  26.     }
  27.  
  28.     public static int get_area_count(int[][] mat, int threshold, int c) {
  29.         int n = mat.length;
  30.         int m = mat[0].length;
  31.         int[][] s = new int [n+1][m+1];
  32.         //1、生成前缀和子矩阵
  33.         for (int i = 1; i <= n; ++i){
  34.             for (int j = 1; j <= m; ++j) {
  35.                 //s[i][j]表示以[i,j]作为矩阵最右下角的最大矩阵的前缀和
  36.                 //解释：以点[i,j]作为作为最右下角的最大矩阵的前缀和需要加上点[i-1,j]和点[i,j-1]的前缀和，然而会重复多加一个点[i-1][j-1]的前缀和，所以要减一个
  37.                 s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + mat[i - 1][j - 1];
  38.             }
  39.         }
  40.         int ans = 0;
  41.         //2、遍历前缀和矩阵，获得边长等于c的矩阵
  42.         for (int i = c; i <= n; ++i) {
  43.             for (int j = c; j <= m; ++j) {
  44.                 //重点理解：减去点[i-c][j]和点[i][j-c]的矩阵前缀和，剩下来的为一个边长为c正方形，注意点[i-c][j-c]减了两次，需要加一个回来
  45.                 if (s[i][j] - s[i - c][j] - s[i][j - c] + s[i - c][j - c] >= threshold)
  46.                     ans += 1;
  47.             }
  48.         }
  49.         return ans;
  50.     }
  51.  
  52. }

【最大连续文件之和 / 区块链文件转储系统 】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4. import java.math.BigInteger;
  5. import java.util.stream.Stream;
  6.  
  7. class Main {
  8.     public static void main(String[] args) {
  9.         // 处理输入
  10.         Scanner in = new Scanner(System.in);
  11.         int M =in.nextInt();
  12.         in.nextLine();
  13.         Integer[] F = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
  14.  
  15.         // 窗口左右边界
  16.         int left = 0, right = 0;
  17.         //窗口和
  18.         int window_sum = 0;
  19.         //最大窗口和
  20.         int window_max = 0;
  21.     
  22.         while (right < F.length) {
  23.             int temp = window_sum + F[right];
  24.         
  25.             // 窗口内总和大了，sum减去左边界，左端边界+1
  26.             if (temp > M) {
  27.                 window_sum -= F[left]; 
  28.                 left += 1;
  29.             }
  30.             // 窗口内总和小了，右边界+1，sum加上右边界
  31.             else if (temp < M) {
  32.                 window_sum += F[right];
  33.                 window_max = Math.max(window_sum, window_max);
  34.                 right += 1;
  35.             }
  36.             // 窗口内总和==M，直接return
  37.             else {
  38.                 System.out.println(M);
  39.                 return;
  40.             }
  41.         }
  42.  
  43.         System.out.println(window_max);
  44.     }
  45.  
  46. }

【发现新词的数量 /新词挖掘】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4. import java.math.BigInteger;
  5. import java.util.stream.Stream;
  6.  
  7. class Main {
  8.     public static void main(String[] args) {
  9.         // 处理输入
  10.         Scanner in = new Scanner(System.in);
  11.         String content = in.nextLine();
  12.         String word = in.nextLine();
  13.         System.out.println(contin(content, word));
  14.     }
  15.  
  16.     public static int contin(String content, String word){
  17.         if(content.length() < word.length())
  18.             return 0;
  19.         if(word.length() == 0)
  20.             return 0;
  21.         HashMap<Character, Integer> content_map = new HashMap<Character, Integer>();
  22.         HashMap<Character, Integer> word_map = new HashMap<Character, Integer>();
  23.         //先统计出word中的字符组成
  24.         for (int i=0;i<word.length();i++)
  25.             word_map.put(word.toCharArray()[i], word_map.getOrDefault(word.toCharArray()[i], 0) + 1);
  26.  
  27.         char[] content_arr = content.toCharArray();
  28.         int word_char_kind = word_map.size();
  29.         int right = 0;
  30.         int content_child_char_kind = 0;
  31.         int result = 0;
  32.         while(right < content.length()){     
  33.             if(right >= word.length()){
  34.                 int left = right - word.length();
  35.                 if (word_map.containsKey(content_arr[left]) && word_map.get(content_arr[left]) == content_map.get(content_arr[left]))
  36.                     content_child_char_kind -=1 ;
  37.                 content_map.put(content_arr[left], content_map.getOrDefault(content_arr[left], 0) - 1);
  38.                     
  39.             }
  40.             
  41.             content_map.put(content_arr[right], content_map.getOrDefault(content_arr[right], 0) + 1);
  42.             if (word_map.containsKey(content_arr[right]) && word_map.get(content_arr[right]) == content_map.get(content_arr[right]))
  43.                 content_child_char_kind+=1;
  44.             right+=1;
  45.             if (content_child_char_kind == word_char_kind) {
  46.                 result += 1;
  47.             }
  48.         }
  49.         return result;
  50.     }
  51.  
  52.  
  53. }

【最接最大输出功率的设备 /查找充电设备组合】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4. import java.math.BigInteger;
  5. import java.util.stream.Stream;
  6.  
  7. class Main {
  8.     public static void main(String[] args) {
  9.         // 处理输入
  10.         Scanner in = new Scanner(System.in);
  11.         int n = in.nextInt();
  12.         in.nextLine();
  13.         Integer[] p = Arrays.stream(in.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
  14.         int p_max = in.nextInt();
  15.  
  16.         //dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
  17.         int[][] dp = new int[n + 1][p_max + 1];
  18.  
  19.         // 初始化, i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
  20.         for (int j = p_max; j >= p[0]; j--) {
  21.             dp[0][j] = dp[0][j - p[0]] + p[0];
  22.         }
  23.  
  24.         for (int i = 1; i < n; i++) {  // 遍历物品
  25.             for (int j = 0; j <= p_max; j++) { // 遍历背包容量
  26.                 // 背包容量为j，如果物品i的体积，此时dp[i][j]就是dp[i - 1][j]
  27.                 if (j < p[i]) {
  28.                     dp[i][j] = dp[i - 1][j];
  29.                 } else {
  30.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - p[i]] + p[i]);
  31.                 }
  32.             }
  33.         }
  34.     
  35.         System.out.println(dp[n-1][p_max]);
  36.         
  37.     }
  38.  
  39.  
  40. }

【计算是否能达到公司 /上班之路】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4.  
  5. class Main {
  6.     private static final int[][] directions = {{0, 1, 1}, {0, -1, 2}, {1, 0, 3}, {-1, 0, 4}};
  7.     private static int t, c, n, m;
  8.     private static String[][] matrix;
  9.     
  10.     public static void main(String[] args) {
  11.         // 处理输入
  12.         Scanner in = new Scanner(System.in);
  13.         t = in.nextInt();
  14.         c = in.nextInt();
  15.     
  16.         n = in.nextInt();
  17.         m = in.nextInt();
  18.     
  19.         matrix = new String[n][m];
  20.         for (int i = 0; i < n; i++) {
  21.             matrix[i] = in.next().split("");
  22.         }
  23.  
  24.         //遍历矩阵,找到起点
  25.         for (int i = 0; i < n; i++) {
  26.             for (int j = 0; j < m; j++) {
  27.                 boolean[][] visited = new boolean[m][n];
  28.                 if ("S".equals(matrix[i][j])) {
  29.                     if (dfs(visited, i, j, 0, 0, 0)) {
  30.                         System.out.println("YES");
  31.                         return;
  32.                     } else {
  33.                         System.out.println("NO");
  34.                         return;
  35.                     }
  36.                 }
  37.             }
  38.         }
  39.         System.out.println("NO");
  40.         return;
  41.     }
  42.  
  43.     public static boolean dfs(boolean[][] visited, int x, int y, int ut, int uc, int last_direct) {
  44.         // 找到目的地
  45.         if ("T".equals(matrix[x][y])) {
  46.             return true;
  47.         }
  48.         //表示当前点已走过
  49.         visited[x][y] = true;
  50.  
  51.         // 有四个方向选择走下一步
  52.         for (int[] direction : directions) {
  53.             int direct = direction[2];
  54.             int new_x = x + direction[0];
  55.             int new_y = y + direction[1];
  56.         
  57.             // 转向+破壁标记
  58.             boolean turn_flag = false;
  59.             boolean break_flag = false;
  60.  
  61.             // 越界 + 是否当前点已访问判断
  62.             if (new_x >= 0 && new_x < n && new_y >= 0 && new_y < m && !visited[new_x][new_y]) {
  63.  
  64.                 //转向+破壁判断
  65.                 if (last_direct != 0 && last_direct != direct) {
  66.                     // 转向次数已用尽
  67.                     if (ut + 1 > t) {
  68.                         continue;
  69.                     }
  70.                     turn_flag = true;
  71.                 }
  72.         
  73.                 if ("*".equals(matrix[new_x][new_y])) {
  74.                     // 破壁次数已用尽
  75.                     if (uc + 1 > c) {
  76.                         continue;
  77.                     }
  78.                     break_flag = true;
  79.                 }
  80.                 // 可到达目的地T, 返回true
  81.                 if (dfs(visited, new_x, new_y, ut + (turn_flag ? 1 : 0), uc + (break_flag ? 1 : 0), direct)) {
  82.                     return true;
  83.                 }
  84.             }
  85.         }
  86.         return false;
  87.     }
  88.  
  89. }

【简单的解压缩算法】【2023 Q1 | 200分】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4.  
  5. class Main {
  6.     public static void main(String[] args) {
  7.         // 处理输入
  8.         Scanner in = new Scanner(System.in);
  9.         //防止最后一个字符是数字
  10.         String input_str = in.nextLine() + " ";
  11.         LinkedList<String> stack = new LinkedList<>();
  12.         // bracket_pos 保存的是所有花括号出现的位置
  13.         LinkedList<Integer> bracket_pos = new LinkedList<>();
  14.         // 保存数字的字符串
  15.         String number_str = "";
  16.  
  17.         for (int i = 0; i < input_str.length(); i++) {
  18.             char c = input_str.charAt(i);
  19.             //数字
  20.             if (c >= '0' && c <= '9') { 
  21.                 number_str += c;
  22.                 continue;
  23.             }
  24.  
  25.             if (number_str.length() > 0) {
  26.                 int repeat_count = Integer.parseInt(number_str); 
  27.                 number_str = "";
  28.                 // 若此时栈顶是 } 字符, 将对应的字母重复repeat_count次
  29.                 if ("}".equals(stack.getLast())) { 
  30.                     //获取上一个 { 的位置
  31.                     int pos = bracket_pos.removeLast();
  32.                     //删除左右{}
  33.                     stack.remove(pos); 
  34.                     stack.removeLast(); 
  35.                     // 重复{}之间的字母
  36.                     repeat_operation(stack, pos, repeat_count); 
  37.                 } else { 
  38.                     //不是 } 字符, 简单重复栈顶字符对应次即可
  39.                     repeat_operation(stack, stack.size() - 1, repeat_count);
  40.                 }
  41.             }
  42.  
  43.             // { 字符
  44.             if (c == '{') {
  45.                 bracket_pos.add(stack.size());
  46.             }
  47.  
  48.  
  49.             // 其他字符 (字母 + })
  50.             stack.add(c + "");
  51.         }
  52.  
  53.         // 输出
  54.         System.out.println(stack.stream().collect(Collectors.joining())); 
  55.     }
  56.  
  57.     // 重复{}内的字母, 并重新入栈
  58.     public static void repeat_operation(LinkedList<String> stack, int pos, int repeat_count) {
  59.         int count = stack.size() - pos;
  60.  
  61.         // temp_stack用于存储弹栈数据
  62.         String[] temp_stack = new String[count];
  63.  
  64.         while (count >= 1) {
  65.             count -= 1;
  66.             temp_stack[count] = stack.removeLast();
  67.         }
  68.         
  69.         String temp_str = String.join("", temp_stack);
  70.         StringBuilder result = new StringBuilder();
  71.         //重复repeat_count次
  72.         for (int i = 0; i < repeat_count; i++) {
  73.             result.append(temp_str);
  74.         }
  75.  
  76.         stack.add(result.toString());
  77.     }
  78.  
  79. }

【修建高铁最优成本 /最优高铁城市修建方案】

  1. import java.util.Scanner;
  2. import java.util.*;
  3. import java.util.stream.Collectors;
  4.  
  5. class Main {
  6.     public static void main(String[] args) {
  7.         // 处理输入
  8.         Scanner in = new Scanner(System.in);
  9.         int n = in.nextInt();
  10.         int pair_count_1 = in.nextInt();
  11.         int pair_count_2 = in.nextInt();
  12.     
  13.         // 可建设高铁的两城市
  14.         int[][] city_pair_1 = new int[pair_count_1][3];
  15.         for (int i = 0; i < pair_count_1; i++) {
  16.             city_pair_1[i][0] = in.nextInt();
  17.             city_pair_1[i][1] = in.nextInt();
  18.             city_pair_1[i][2] = in.nextInt();
  19.         }
  20.     
  21.         // 必建高铁的两城市
  22.         int[][] city_pair_2 = new int[pair_count_2][2];
  23.         for (int i = 0; i < pair_count_2; i++) {
  24.             city_pair_2[i][0] = in.nextInt();
  25.             city_pair_2[i][1] = in.nextInt();
  26.         }
  27.  
  28.         UF uf = new UF(n);
  29.  
  30.         // key为修建高铁的两个城市，value为费用
  31.         HashMap<String, Integer> city_map = new HashMap<>();
  32.         for (int[] city_pair : city_pair_1) {
  33.             int city1 = city_pair[0], city2 = city_pair[1];
  34.             city_map.put(city1 < city2 ? city1 + "-" + city2 : city2 + "-" + city1, city_pair[2]);
  35.         }
  36.     
  37.         int result = 0;
  38.         // 先计算必建高铁情况下的费用
  39.         for (int[] city_pair : city_pair_2) {
  40.             int city1 = city_pair[0], city2 = city_pair[1];
  41.             result += city_map.get(city1 < city2 ? city1 + "-" + city2 : city2 + "-" + city1);
  42.             // 纳入并查集
  43.             uf.union(city1, city2);
  44.         }
  45.         System.out.println(result);
  46.     
  47.         //  已经满足所有城市通车，直接返回
  48.         if (uf.count == 1) {
  49.             System.out.println(result);
  50.             return;
  51.         }
  52.     
  53.         // 按修建费用排序
  54.         Arrays.sort(city_pair_1, (a, b) -> a[2] - b[2]);
  55.     
  56.         for (int[] city_pair : city_pair_1) {
  57.             int city1 = city_pair[0], city2 = city_pair[1];
  58.             // 判断两城市是否相连
  59.             if (uf.item[city1] != uf.item[city2]) {
  60.                 uf.union(city1, city2);
  61.                 // 若可以合入，则将对应的建造成本计入result
  62.                 result += city_pair[2];
  63.             }
  64.             if (uf.count == 1) {
  65.                 break;
  66.             }
  67.         }
  68.     
  69.         // count>1代表有的城市无法通车
  70.         if (uf.count > 1) {
  71.             System.out.println(-1);
  72.             return;
  73.         }
  74.     
  75.         System.out.println(result);
  76.     }
  77.  
  78. }
  79.  
  80. // 并查集
  81. class UF {
  82.   int[] item;
  83.   int count;
  84.  
  85.   public UF(int n) {
  86.     item = new int[n + 1];
  87.     count = n;
  88.     for (int i = 0; i < n; i++) item[i] = i;
  89.   }
  90.  
  91.   public int find(int x) {
  92.     if (x != item[x]) {
  93.       return (item[x] = find(item[x]));
  94.     }
  95.     return x;
  96.   }
  97.  
  98.   public void union(int x, int y) {
  99.     int x_item = find(x);
  100.     int y_item = find(y);
  101.  
  102.     if (x_item != y_item) {
  103.       item[y_item] = x_item;
  104.       count--;
  105.     }
  106.   }
  107. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/121274
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号