You are viewing a single comment's thread. Return to all comments →
@anoohyabollampa1: FYI, the following Java 8 Solution has passed all test cases:
static java.util.function.IntUnaryOperator find; static int[] componentsInGraph(int[][] gb) { int N = gb.length; int n = 2*N + 1; int[] parent = java.util.stream.IntStream.range(0, n).toArray(); int[] size = java.util.stream.IntStream.range(0, n).map(i -> 1).toArray(); // Find by Path Compression find = x -> { if(parent[x]!=x) parent[x]=find.applyAsInt(parent[x]); return parent[x]; }; // Union by Size for(int[] edge: gb) { int root1 = find.applyAsInt(edge[0]); int root2 = find.applyAsInt(edge[1]); if(root1 == root2) continue; if(size[root1] > size[root2]) { int r = root1; root1 = root2; root2 = r; } parent[root1] = root2; size[root2] += size[root1]; size[root1] = 0; } IntSummaryStatistics s = Arrays.stream(size) .filter(i -> i>1) .summaryStatistics(); return new int[]{s.getMin(), s.getMax()}; }
Seems like cookies are disabled on this browser, please enable them to open this website
Components in a graph
You are viewing a single comment's thread. Return to all comments →
@anoohyabollampa1: FYI, the following Java 8 Solution has passed all test cases:
Java 8 Solution in O(N) with Disjoint Set