###### tags: `Leetcode` `medium` `graph` `bfs` `python` `c++`

# 547. Number of Provinces

## [題目連結:] https://leetcode.com/problems/number-of-provinces/

## 題目:
There are ```n``` cities. Some of them are connected, while some are not. If city ```a``` is connected directly with city ```b```, and city ```b``` is connected directly with city ```c```, then city ```a``` is connected indirectly with city ```c```.

A **province** is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an ```n x n``` matrix ```isConnected``` where ```isConnected[i][j] = 1``` if the ```ith``` city and the ```jth``` city are directly connected, and ```isConnected[i][j] = 0``` otherwise.

Return the total number of **provinces**.


## 解題想法:
* 此有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那麼城市 a 與城市 c 間接相連。
* 省份province 是一組直接或間接相連的城市，組內不含其他沒有相連的城市。
* 給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。
* 返回矩陣中 省份 的數量。

* 可視為求連通分量個數
* 初始:
* visited=set(): 紀錄已拜訪過的點
* que=[] :BFS用
* 技巧:
* **直接遍歷isConnected的第一維陣列(視為該點)就好**
* **因為isConnected的二維只是紀錄跟其他人的關係**
* for i in range(len(isConnected)):
* 每次判斷該點是否已經拜訪過
* 若已拜訪，則continue
* 尚未拜訪
* 將該點加入que、visited
* 最終結果res+=1
* while que: 判斷以當前node為主連通圖
* 對於isConnected的二維關係進行判斷
* 若鄰居尚未拜訪且於isConnect值為1
* 將鄰居加入que與visited

## Python:

class Solution(object):
    def findCircleNum(self, isConnected):
        """
        :type isConnected: List[List[int]]
        :rtype: int
        """
        m=len(isConnected)
        n=len(isConnected[0])
        que=[] #bfs用
        visited=set() #紀錄已拜訪過的點 用set避免重複
        res=0
        #直接run isConnected的第一維陣列(視為該點)就好 
        #因為二維只是紀錄跟其他人的關係
        for i in range(m):
            if i in visited: #若該點已經訪問過
                continue
            visited.add(i)
            que.append(i)
            res+=1
            #bfs
            while que:
                cur=que.pop(0)
                #判斷二維
                for neighber in range(n):
                    if (neighber not in visited) and (isConnected[cur][neighber]==1):
                        visited.add(neighber)
                        que.append(neighber)
        return res

## C++:

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int m=isConnected.size();
        int n=isConnected[0].size();
        int res=0;
        queue<int> que;
        //use 'count' to check whether an element exists
        unordered_set<int> visited; 
        for (int i=0; i<m; i++){
            if (visited.count(i))
                continue;
            visited.insert(i);
            que.push(i);
            res+=1;
            //check connect component
            while (!que.empty()){
                int cur=que.front(); que.pop();
                for (int neighber=0; neighber<n; neighber++){
                    if (!visited.count(neighber) && isConnected[cur][neighber]==1){
                        visited.insert(neighber);
                        que.push(neighber);
                    }
                }
            }
        }
        return res;
    }
};