You are viewing a single comment's thread. Return to all comments →
My BFS based solution:
static class GraphNode { int x; List<GraphNode> neighbors; boolean visited; public GraphNode(int x) { this.x = x; this.neighbors = new ArrayList<>(); } } static int[] componentsInGraph(int[][] gb) { Map<Integer, GraphNode> nodes = buildGraph(gb); int min = Integer.MAX_VALUE; int max = 0; for(GraphNode g : nodes.values()) { int curCount = 0; Queue<GraphNode> q = new LinkedList<>(); q.add(g); while(!q.isEmpty()) { GraphNode poppedNode = q.remove(); if(poppedNode.visited) { continue; } ++curCount; poppedNode.visited = true; for(GraphNode neighbor : poppedNode.neighbors) { q.add(neighbor); } } if(curCount > max) { max = curCount; } if(curCount < min && curCount > 1) { min = curCount; } } return new int[]{min, max}; } private static Map<Integer, GraphNode> buildGraph(int[][] gb) { Map<Integer, GraphNode> sg = new HashMap<>(); for(int i = 0; i < gb.length; ++i) { int n1 = gb[i][0]; int n2 = gb[i][1]; GraphNode gn1 = sg.computeIfAbsent(n1, (v) -> new GraphNode(n1)); GraphNode gn2 = sg.computeIfAbsent(n2, (v) -> new GraphNode(n2)); gn1.neighbors.add(gn2); gn2.neighbors.add(gn1); } return sg; }
Components in a graph
You are viewing a single comment's thread. Return to all comments →
My BFS based solution: