###### tags: `Leetcode` `medium` `graph` `dfs` `union find` `python` `c++`

# 947. Most Stones Removed with Same Row or Column

## [題目連結:] https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/description/

## 題目:
On a 2D plane, we place ```n``` stones at some integer coordinate points. Each coordinate point may have at most one stone.

A stone can be removed if it shares either **the same row or the same column** as another stone that has not been removed.

Given an array ```stones``` of length ```n``` where ```stones[i] = [xi, yi]``` represents the location of the ```ith``` stone, return the largest possible number of stones that can be removed.

**Example 1:**

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation: One way to remove 5 stones is as follows:
1. Remove stone [2,2] because it shares the same row as [2,1].
2. Remove stone [2,1] because it shares the same column as [0,1].
3. Remove stone [1,2] because it shares the same row as [1,0].
4. Remove stone [1,0] because it shares the same column as [0,0].
5. Remove stone [0,1] because it shares the same row as [0,0].
Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.

**Example 2:**

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Explanation: One way to make 3 moves is as follows:
1. Remove stone [2,2] because it shares the same row as [2,0].
2. Remove stone [2,0] because it shares the same column as [0,0].
3. Remove stone [0,2] because it shares the same row as [0,0].
Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.

**Example 3:**

Input: stones = [[0,0]]
Output: 0
Explanation: [0,0] is the only stone on the plane, so you cannot remove it.

## 解題想法:
* 此題為，給n個石頭的座標，同行or同列的石頭都要移除，求最多移除個數
* 流程:
* 求**連通子圖的個數**,每個連通圖即為1個石頭，剩下的全移除
* Step1:
* 建立graph
* key: position in stones
* value: list[]存相連的位置
* 雙迴圈進行判斷
* 若兩位置的x或y相等，則相連
* Step2:
* visited=[False]* len(stones)
* 紀錄每個位置是否拜訪過
* res=0
* 紀錄連通子圖個數
* Step3:
* 遍歷每個位置 for i in range(len(stones)):
* 對於尚未拜訪的i進行後續Step4操作
* Step4:
* res+=1
* visited[i]=True
* 將鄰居、鄰居的鄰居皆改為True
* que=[i]
* while que判斷
* Step5:
* return 要刪掉的node數=len(stones)-連通子圖個數

## Python:

from collections import defaultdict
class Solution(object):
    def removeStones(self, stones):
        """
        :type stones: List[List[int]]
        :rtype: int
        """
        #找出連通子圖的個數
        graph=defaultdict(list) #key: pos in stones ; value: node which connected
        #connect the graph
        for pos1, coordinate1 in enumerate(stones):
            for pos2 in range(pos1):
                coordinate2=stones[pos2]
                if coordinate1[0]==coordinate2[0] or coordinate1[1]==coordinate2[1]:
                    graph[pos1].append(pos2)
                    graph[pos2].append(pos1)
        visited=[False]*len(stones)
        res=0 #紀錄連通子圖個數
        for i in range(len(stones)):
            if not visited[i]: #尚未拜訪
                res+=1
                visited[i]=True
                #鄰居、鄰居的鄰居皆改為False
                que=[i]
                while que:
                    curPos=que.pop(0)
                    for neighber in graph[curPos]:
                        if not visited[neighber]:
                            visited[neighber]=True
                            que.append(neighber)
                    
        #return 要刪掉的node數=len(stones)-連通子圖數
        return len(stones)-res 

## C++:

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        unordered_map<int, vector<int>> graph;
        int n=stones.size();
        //connect the graph
        for (int pos1=0; pos1<n; pos1++){
            for (int pos2=0; pos2<pos1; pos2++){
                if (stones[pos1][0]==stones[pos2][0] || stones[pos1][1]==stones[pos2][1]){
                    graph[pos1].push_back(pos2);
                    graph[pos2].push_back(pos1);
                }
            }
        }
        vector<bool> visited(n,false);
        int res=0;
        //dfs
        for (int i=0; i<n; i++){
            if (!visited[i]){
                res+=1;
                visited[i]=true;
                queue<int> que;
                que.push(i);
                //let visited[neighber]=true
                while (!que.empty()){
                    int curPos=que.front(); que.pop();
                    for (auto neighber: graph[curPos]){
                        if (!visited[neighber]){
                            visited[neighber]=true;
                            que.push(neighber);
                        }
                    }
                }
            }
        }
        return n-res;
    }
};