Solution
Approach 1: DepthFirst Search
Intuition
Let's say two stones are connected by an edge if they share a row or column, and define a connected component in the usual way for graphs: a subset of stones so that there doesn't exist an edge from a stone in the subset to a stone not in the subset. For convenience, we refer to a component as meaning a connected component.
The main insight is that we can always make moves that reduce the number of stones in each component to 1.
Firstly, every stone belongs to exactly one component, and moves in one component do not affect another component.
Now, consider a spanning tree of our component. We can make moves repeatedly from the leaves of this tree until there is one stone left.
Algorithm
To count connected components of the above graph, we will use depthfirst search.
For every stone not yet visited, we will visit it and any stone in the same connected component. Our depthfirst search traverses each node in the component.
For each component, the answer changes by 1 + component.size
.
Complexity Analysis

Time Complexity: , where is the length of
stones
. 
Space Complexity: .
Approach 2: UnionFind
Intuition
As in Approach 1, we will need to consider components of an underlying graph. A "Disjoint Set Union" (DSU) data structure is ideal for this.
We will skip the explanation of how a DSU structure is implemented. Please refer to https://leetcode.com/problems/redundantconnection/solution/ for a tutorial on DSU.
Algorithm
Let's connect row i
to column j
, which will be represented by j+10000
. The answer is the number of components after making all the connections.
Note that for brevity, our DSU
implementation does not use unionbyrank. This makes the asymptotic time complexity larger.
Complexity Analysis

Time Complexity: , where is the length of
stones
. (If we used unionbyrank, this can be , where is the InverseAckermann function.) 
Space Complexity: .
Analysis written by: @awice.