@@ -1,3 +1,6 @@
+import java.util.ArrayList;
+import java.util.Arrays;
+
 class DSU {
 	private int n;
 	private int[] parentOrSize;
@@ -57,13 +60,14 @@ ArrayList<ArrayList<Integer>> groups() {
 			leaderBuf[i] = leader(i);
 			groupSize[leaderBuf[i]]++;
 		}
-		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
+		ArrayList<ArrayList<Integer>> result = new ArrayList<>(n);
 		for (int i = 0; i < n; i++) {
-			result.add(new ArrayList<>());
+			result.add(new ArrayList<>(groupSize[i]));
 		}
 		for (int i = 0; i < n; i++) {
 			result.get(leaderBuf[i]).add(i);
 		}
+		result.removeIf(ArrayList::isEmpty);
 		return result;
 	}
 }
Original file line number	Diff line number	Diff line change
`@@ -1,3 +1,6 @@`
	`1`	`+import java.util.ArrayList;`
	`2`	`+import java.util.Arrays;`
	`3`	`+`
`1`	`4`	`class DSU {`
`2`	`5`	`private int n;`
`3`	`6`	`private int[] parentOrSize;`
`@@ -57,13 +60,14 @@ ArrayList<ArrayList<Integer>> groups() {`
`57`	`60`	`leaderBuf[i] = leader(i);`
`58`	`61`	`groupSize[leaderBuf[i]]++;`
`59`	`62`	`}`
`60`		`- ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();`
	`63`	`+ ArrayList<ArrayList<Integer>> result = new ArrayList<>(n);`
`61`	`64`	`for (int i = 0; i < n; i++) {`
`62`		`- result.add(new ArrayList<>());`
	`65`	`+ result.add(new ArrayList<>(groupSize[i]));`
`63`	`66`	`}`
`64`	`67`	`for (int i = 0; i < n; i++) {`
`65`	`68`	`result.get(leaderBuf[i]).add(i);`
`66`	`69`	`}`
	`70`	`+ result.removeIf(ArrayList::isEmpty);`
`67`	`71`	`return result;`
`68`	`72`	`}`
`69`	`73`	`}`