Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedWriter;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.util.*;
- public class Solution {
- private static class Graph {
- private final Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
- private void add(int a, int b) {
- List<Integer> edges = null;
- if (adjacencyList.containsKey(a)) {
- edges = adjacencyList.get(a);
- } else {
- edges = new ArrayList<>();
- }
- edges.add(b);
- adjacencyList.put(a, edges);
- }
- public int maxRegion() {
- List<Set<Integer>> regions = new ArrayList<>();
- Set<Integer> visited = new HashSet<>();
- for (int node : adjacencyList.keySet()) {
- if (visited.contains(node)) {
- continue;
- }
- Set<Integer> region = dfs(node);
- visited.addAll(region);
- mergeRegions(regions, region);
- }
- int max = -1;
- for (Set<Integer> region : regions) {
- max = Math.max(max, edgesInRegion(region));
- }
- return max;
- }
- private void mergeRegions(List<Set<Integer>> regions, Set<Integer> currentRegion) {
- System.out.println("Mergion regions " + regions + " " + currentRegion);
- for (int r : currentRegion) {
- for (Set<Integer> region: regions) {
- if (region.contains(r)) {
- region.addAll(currentRegion);
- return;
- }
- }
- }
- regions.add(currentRegion);
- }
- private Set<Integer> dfs(int node) {
- Stack<Integer> stack = new Stack<>();
- Set<Integer> visited = new HashSet<>();
- Set<Integer> region = new HashSet<>();
- stack.push(node);
- while (!stack.isEmpty()) {
- int current = stack.pop();
- if (visited.contains(current)) {
- continue;
- }
- region.add(current);
- visited.add(current);
- for (int edges : adjacencyList.get(current)) {
- stack.push(edges);
- }
- }
- return region;
- }
- private int edgesInRegion(Set<Integer> region) {
- int edges = 0;
- for (int node : region) {
- edges += adjacencyList.get(node).size();
- }
- return edges;
- }
- }
- static int maxRegion(int[][] grid) {
- Graph g = new Graph();
- for (int i = 0; i < grid.length; i++) {
- for (int j = 0; j < grid[0].length; j++) {
- if (grid[i][j] == 1) {
- g.add(i, j);
- }
- }
- }
- return g.maxRegion();
- }
- private static final Scanner scanner = new Scanner(System.in);
- public static void main(String[] args) throws IOException {
- BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
- int n = scanner.nextInt();
- scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
- int m = scanner.nextInt();
- scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
- int[][] grid = new int[n][m];
- for (int i = 0; i < n; i++) {
- String[] gridRowItems = scanner.nextLine().split(" ");
- scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
- for (int j = 0; j < m; j++) {
- int gridItem = Integer.parseInt(gridRowItems[j]);
- grid[i][j] = gridItem;
- }
- }
- int res = maxRegion(grid);
- bufferedWriter.write(String.valueOf(res));
- bufferedWriter.newLine();
- bufferedWriter.close();
- scanner.close();
- }
- }
Add Comment
Please, Sign In to add comment