' \ufeffI need help modifying the code in the picture to meet the…

Question

Manu · Accepted Answer

Solution: Java Code: import java.util.*; public class Main { static class UnionFind { private int[] parent; private int[] rank; private int[] size; public UnionFind(int size) { parent = new int[size]; rank = new int[size]; this.size = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; rank[i] = 1; this.size[i] = 1; } } public int find(int p) { if (parent[p] != p) { parent[p] = find(parent[p]); } return parent[p]; } public void union(int p, int q) { int rootP = find(p); int rootQ = find(q); if (rootP != rootQ) { if (rank[rootP] > rank[rootQ]) { parent[rootQ] = rootP; size[rootP] += size[rootQ]; } else if (rank[rootP] < rank[rootQ]) { parent[rootP] = rootQ; size[rootQ] += size[rootP]; } else { parent[rootQ] = rootP; rank[rootP]++; size[rootP] += size[rootQ]; } } } public boolean connected(int p, int q) { return find(p) == find(q); } public int componentSize(int p) { return size[find(p)]; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int d = scanner.nextInt(); int[][] connections = new int[m][2]; for (int i = 0; i < m; i++) { connections[i][0] = scanner.nextInt() - 1; connections[i][1] = scanner.nextInt() - 1; } int[] destructions = new int[d]; for (int i = 0; i < d; i++) { destructions[i] = scanner.nextInt() - 1; } UnionFind uf = new UnionFind(n); boolean[] activeConnections = new boolean[m]; Arrays.fill(activeConnections, true); for (int i : destructions) { activeConnections[i] = false; } for (int i = 0; i < m; i++) { if (activeConnections[i]) { uf.union(connections[i][0], connections[i][1]); } } List results = new ArrayList<>(); results.add(calculateConnectivity(uf, n)); for (int i = d - 1; i >= 0; i--) { int connIdx = destructions[i]; uf.union(connections[connIdx][0], connections[connIdx][1]); results.add(calculateConnectivity(uf, n)); } Collections.reverse(results); for (int result : results) { System.out.println(result); } } private static int calculateConnectivity(UnionFind uf, int n) { int[] componentSizes = new int[n]; for (int i = 0; i < n; i++) { componentSizes[uf.find(i)]++; } int connectivity = 0; for (int size : componentSizes) { if (size > 0) { connectivity += size * size; } } return connectivity; } } Output SS: 9 8 2 1 5 2 3 2 6 3 6 6 7 7 8 7 9 8 9 5 3 41 23 23 Output SS: Explanation Initialization : Read the input and initialize the Disjoint Set. Initial Union : Union all connections except those that are marked for destruction. Reverse Destruction : Re-add the destroyed connections in reverse order to track the connectivity. Output : Print the connectivity results after each reverse addition.

AI tools

Study help

Free tools

Earn & more

Computer science

Computer science

Manu

Answer

Extracted Transcript from Images

AI

Study help

Earn & more

Company