Hard · Bipartite DSU
Understand → Visualise → Practice.
A stone may be removed while another stone shares its row or column. Return the maximum removals.
Stones sharing a row or column form groups. Within a group you can always remove stones until one remains, so the answer is the number of stones minus the number of groups.
Union any two stones that share a row or a column.
Count the distinct roots.
Return stones − groups.
O(n² α(n)) time for the pairwise scan and O(n) space; unioning row and column identifiers instead gives O(n α(n)).
Trying to simulate removals in different orders is exponential; the group count settles it.
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.