You are viewing a single comment's thread. Return to all comments →
Java Solution
class UF { private int[] parent; private int[] size; public UF(int n) { parent = new int[n]; size = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } public int find(int i) { if (i == parent[i]) { return i; } return parent[i] = find(parent[i]); } public void union(int i, int j) { int pi = find(i); int pj = find(j); if (pi != pj) { if (size[pi] > size[pj]) { int tmp = pi; pi = pj; pj = tmp; } parent[pj] = pi; size[pi] += size[pj]; } } public boolean connected(int i, int j) { return find(i) == find(j); } public int getMinSize() { int min = 2; boolean isMinValid = false; for (int i = 0; i < size.length; i++) { int realSize = size[find(i)]; if (!isMinValid && realSize >= 2) { min = realSize; isMinValid = true; } if (isMinValid && realSize >= 2 && realSize < min) { min = realSize; } } return min; } public int getMaxSize() { int max = 2; boolean isMaxValid = false; for (int i = 0; i < size.length; i++) { int realSize = size[find(i)]; if (!isMaxValid && realSize >= 2) { max = realSize; isMaxValid = true; } if (isMaxValid && realSize >= 2 && realSize > max) { max = realSize; } } return max; } } class Result { public static List<Integer> componentsInGraph(List<List<Integer>> gb) { List<Integer> res = new ArrayList<>(); int n = 0; for (List<Integer> list : gb) { int x = list.get(0); int y = list.get(1); n = Math.max(n, x); n = Math.max(n, y); } UF uf = new UF(n); for (List<Integer> list : gb) { uf.union(list.get(0) - 1, list.get(1) - 1); } res.add(uf.getMinSize()); res.add(uf.getMaxSize()); return res; } }
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 →
Java Solution