这道题本质就是 323. Number of Connected Components in an Undirected Graph。

 

DFS O(n^2)

一模一样, 只不过图要自己构建而已。

class Solution {public:    vector
     
      
       > adj;        int removeStones(vector
       
        
         >& stones) {        int n=stones.size();        adj.resize(n,list
         
          ());        for (int i=0;i
          
            visited(n,false); for (int i=0;i
           
             &visited){ if (visited[i]) return; visited[i] = true; for (auto x:adj[i]){ dfs(x,visited); } }};
           
          
         
        
       
      
     

 

Union Find O(n^2)，两两union n^2

class Solution {public:      vector
     
       parent;    int removeStones(vector
      
       
        >& stones) {        int n=stones.size();        parent.resize(n,-1);        for (int i=0;i
        
         parent[root2]){            parent[root2] += parent[root1];            parent[root1] = root2;        }else{            parent[root1] += parent[root2];            parent[root2] = root1;        }    }        int Find(int x){        if (parent[x]<0) return x;        return parent[x]=Find(parent[x]);    }};
        
       
      
     

 

Union Find (Optimized)

Solution里的很取巧的做法。横坐标纵坐标都一起union，这样只要遍历stones一次即可。这里将纵坐标+1000，就能简单区分横纵坐标。

时间复杂度 由于union by size，O(nlogn)。如果用union by rank来写，可以 O(n*α(n))。

class Solution {public:       vector
     
       parent;        int removeStones(vector
      
       
        >& stones) {        int n=stones.size();        parent.resize(20000,-1);        for (auto stone:stones){            int x=stone[0], y=stone[1];            Union(x,y+10000);        }        unordered_set
        
          s;        for (auto stone:stones){            s.insert(Find(stone[0]));        }        return n-s.size();        return 0;    }        void Union(int x, int y){ // union by size        int root1=Find(x), root2=Find(y);        if (root1==root2) return;        if (parent[root1]>parent[root2]){            parent[root2] += parent[root1];            parent[root1] = root2;        }else{            parent[root1] += parent[root2];            parent[root2] = root1;        }    }        int Find(int x){        if (parent[x]<0) return x;        return parent[x]=Find(parent[x]);    }};