Guest User

Untitled

a guest
Jul 21st, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.93 KB | None | 0 0
  1. import java.io.BufferedWriter;
  2. import java.io.FileWriter;
  3. import java.io.IOException;
  4. import java.util.*;
  5.  
  6. public class Solution {
  7. private static class Graph {
  8. private final Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
  9.  
  10. private void add(int a, int b) {
  11.  
  12. List<Integer> edges = null;
  13.  
  14. if (adjacencyList.containsKey(a)) {
  15. edges = adjacencyList.get(a);
  16. } else {
  17. edges = new ArrayList<>();
  18. }
  19.  
  20.  
  21. edges.add(b);
  22. adjacencyList.put(a, edges);
  23. }
  24.  
  25. public int maxRegion() {
  26. List<Set<Integer>> regions = new ArrayList<>();
  27.  
  28. Set<Integer> visited = new HashSet<>();
  29.  
  30. for (int node : adjacencyList.keySet()) {
  31.  
  32. if (visited.contains(node)) {
  33. continue;
  34. }
  35.  
  36. Set<Integer> region = dfs(node);
  37.  
  38. visited.addAll(region);
  39. mergeRegions(regions, region);
  40. }
  41.  
  42. int max = -1;
  43.  
  44. for (Set<Integer> region : regions) {
  45. max = Math.max(max, edgesInRegion(region));
  46. }
  47.  
  48. return max;
  49. }
  50.  
  51. private void mergeRegions(List<Set<Integer>> regions, Set<Integer> currentRegion) {
  52. System.out.println("Mergion regions " + regions + " " + currentRegion);
  53. for (int r : currentRegion) {
  54. for (Set<Integer> region: regions) {
  55. if (region.contains(r)) {
  56. region.addAll(currentRegion);
  57. return;
  58. }
  59. }
  60. }
  61.  
  62. regions.add(currentRegion);
  63. }
  64.  
  65. private Set<Integer> dfs(int node) {
  66. Stack<Integer> stack = new Stack<>();
  67.  
  68. Set<Integer> visited = new HashSet<>();
  69.  
  70. Set<Integer> region = new HashSet<>();
  71.  
  72. stack.push(node);
  73.  
  74. while (!stack.isEmpty()) {
  75. int current = stack.pop();
  76. if (visited.contains(current)) {
  77. continue;
  78. }
  79.  
  80. region.add(current);
  81. visited.add(current);
  82.  
  83. for (int edges : adjacencyList.get(current)) {
  84. stack.push(edges);
  85. }
  86. }
  87.  
  88. return region;
  89. }
  90.  
  91. private int edgesInRegion(Set<Integer> region) {
  92. int edges = 0;
  93.  
  94. for (int node : region) {
  95. edges += adjacencyList.get(node).size();
  96. }
  97.  
  98. return edges;
  99. }
  100.  
  101.  
  102. }
  103.  
  104. static int maxRegion(int[][] grid) {
  105. Graph g = new Graph();
  106. for (int i = 0; i < grid.length; i++) {
  107. for (int j = 0; j < grid[0].length; j++) {
  108. if (grid[i][j] == 1) {
  109. g.add(i, j);
  110. }
  111. }
  112. }
  113.  
  114. return g.maxRegion();
  115.  
  116. }
  117.  
  118. private static final Scanner scanner = new Scanner(System.in);
  119.  
  120. public static void main(String[] args) throws IOException {
  121. BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
  122.  
  123. int n = scanner.nextInt();
  124. scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  125.  
  126. int m = scanner.nextInt();
  127. scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  128.  
  129. int[][] grid = new int[n][m];
  130.  
  131. for (int i = 0; i < n; i++) {
  132. String[] gridRowItems = scanner.nextLine().split(" ");
  133. scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
  134.  
  135. for (int j = 0; j < m; j++) {
  136. int gridItem = Integer.parseInt(gridRowItems[j]);
  137. grid[i][j] = gridItem;
  138. }
  139. }
  140.  
  141. int res = maxRegion(grid);
  142.  
  143. bufferedWriter.write(String.valueOf(res));
  144. bufferedWriter.newLine();
  145.  
  146. bufferedWriter.close();
  147.  
  148. scanner.close();
  149. }
  150. }
Add Comment
Please, Sign In to add comment