547.Number of Provinces
===

###### tags: `Medium`,`Graph`,`DFS`,`BFS`,`Union Find`

[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 i^th^ city and the j^th^ 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

**Example 2:**


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

**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]`

### 解答

#### C++

class DisjointSet {
public:
    vector<int> parent;
    vector<int> size;
    int count;

    DisjointSet(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; i ++) {
            parent[i] = i;
        }
        count = n;
    }
    int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
    bool isConnected(int p, int q) {
        return find(p) == find(q);
    }
    void union_(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) {
            return ;
        }
        if (size[rootP] < size[rootQ]) {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        } else {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        }
        count --;
    }
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        ios_base::sync_with_stdio(0), cin.tie(0);
        const int CONNECTED = 1;
        int n = isConnected.size();
        if (n == 1) {
            return 1;
        }
        DisjointSet dset(n);
        for (int u = 0; u < n; u ++) {
            for (int v = 0; v < n; v ++) {
                if (isConnected[u][v] == CONNECTED) {
                    dset.union_(u, v);
                }
            }
        }
        return dset.count;
    }
};

> [name=Jerry Wu][time=4 June, 2023]

#### Python

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        ans = 0
        visited = set()

        def dfs(node):
            visited.add(node)
            for child, connect in enumerate(isConnected[node]):
                if connect and child not in visited:
                    dfs(child)
        
        for i in range(n):
            if i not in visited:
                dfs(i)
                ans += 1
        return ans

> [name=Yen-Chi Chen][time=Sun, Jun 4, 2023]

#### C#

public int FindCircleNum(int[][] isConnected) {
    int size = isConnected.Length;
    bool[] visited = new bool[size];

    int provinces = 0;
    for (int i = 0; i < size; i++) {
        if (!visited[i]) {
            provinces++;
            DFS(i);
        } 
    }

    return provinces;

    void DFS(int index) {
        visited[index] = true;
        for (int i = 0; i < size; i++) {
            if (isConnected[index][i] == 1 && !visited[i]) {
                DFS(i);
            }
        }
    }
}

>[name=Jim][time=Jun 6, 2023]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)