# 547. Number of Provinces

###### tags: `leetcode` `DFS` `547` `medium` `BFS` `UNION FIND` `second write: 20210717`
## :memo: Question
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.

### Example 1:


Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
Output: 2

Constraints:
* `1 <= n <= 200`
* `n == isConnected.length`
* `n == isConnected[i].length`
* `isConnected[i][j] is 1 or 0.`
* `isConnected[i][i] == 1`
* `isConnected[i][j] == isConnected[j][i]`

## :memo: leetcode solution
題目上說明給予一個矩陣，代表城市與城市是否有連結，如果有連結則等於 1`(isConnected[i][j] = 1，i,j => 城市i, j)`，然後問你這些城市可以被分成幾群？像題目上給的例子，1.2可以連在一起就是為一個，3自成一個，所以答案是2。
這題我沒有寫出來，之後要多複習，這題可以用 `dfs bfs union-find`，我自己是看了 dfs 的解法。

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        # 首先我們必須有個 visited 的 set 去檢視我們是否已經看過這個城市，
        # 如果看過了就代表他已經被我們歸類在某一區了，就不必再看了。
        visited = set()
        m = len(isConnected)
        count = 0
        
        
        # 查看城市0 與 其他城市j 連結的關係        
        def dfs(i):
            for j in range(m):
                if j not in visited and isConnected[i][j]:
                    # 如果城市0 與 城市j 有關連
                    visited.add(j)
                    # 再繼續訪問 城市j 與其他城市x 的關係
                    dfs(j)        
                
                
        # 然後我們針對 [[1,1,0],[1,1,0],[0,0,1]] 去看 ，
        # 像是我們第一個看的是陣列中的第一個 List 
        # (這個 List 指的意思是 城市0 與 其他城市j 連結的關係 )
        for i in range(m):
            # 檢查是否被我們訪問過了            
            if i not in visited:
                dfs(i)
                count += 1
                    
        return count

# 曾上面的敘述可以知道，這是用dfs 方法去實作的

## :memo: bigO
* 時間複雜度: n^2 (matrix的每個值都看過一遍)
* 空間複雜度: n (set)

## :memo: 第二次寫

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        # dfs 
        # relation == isConnected
        # visited = set()
        
        
        visited = set()
        m = len(isConnected)
        count = 0
        
        def dfs(i):
            
            for j in range(len(isConnected[i])):
                if j not in visited and isConnected[i][j]:
                    visited.add(j)
                    dfs(j)
        
        for i in range(m):
            if i not in visited:
                dfs(i)
                count += 1
                
        return count