# LC 547. Number of Provinces

### [Problem link](https://leetcode.com/problems/number-of-provinces/)

###### tags: `leedcode` `python` `c++` `medium` `Union Find` `DFS`

There are <code>n</code> cities. Some of them are connected, while some are not. If city <code>a</code> is connected directly with city <code>b</code>, and city <code>b</code> is connected directly with city <code>c</code>, then city <code>a</code> is connected indirectly with city <code>c</code>.

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

You are given an <code>n x n</code> matrix <code>isConnected</code> where <code>isConnected[i][j] = 1</code> if the <code>i^th</code> city and the <code>j^th</code> city are directly connected, and <code>isConnected[i][j] = 0</code> otherwise.

Return the total number of **provinces** .

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/24/graph1.jpg" style="width: 222px; height: 142px;" />

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

**Example 2:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/24/graph2.jpg" style="width: 222px; height: 142px;" />

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

**Constraints:**

- <code>1 <= n <= 200</code>
- <code>n == isConnected.length</code>
- <code>n == isConnected[i].length</code>
- <code>isConnected[i][j]</code> is <code>1</code> or <code>0</code>.
- <code>isConnected[i][i] == 1</code>
- <code>isConnected[i][j] == isConnected[j][i]</code>

## Solution 1 - Union Find
#### Python

class UnionFind:
    def __init__(self, size):
        self.root = list(range(size))
        self.rank = [1] * size
        self.provinces = size

    def find(self, x):
        if self.root[x] != x:
            self.root[x] = self.find(self.root[x])
        return self.root[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)

        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
            self.provinces -= 1

    def getProvinces(self):
        return self.provinces

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        uf = UnionFind(n)

        for i in range(n):
            for j in range(i+1, n):
                if isConnected[i][j]:
                    uf.union(i, j)

        return uf.getProvinces()

#### C++

class UnionFind {
public:
    UnionFind(int size) : root(size), rank(size) {
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = root[rootX];
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = root[rootY];
            } else {
                root[rootY] = root[rootX];
                rank[rootX] += 1;
            }
        }
    }

    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }

private:
    vector<int> root;
    vector<int> rank;
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFind uf(isConnected.size());
        int ans = isConnected.size();
        for (int i = 0; i < isConnected.size(); i++) {
            for (int j = 0; j < isConnected[i].size(); j++) {
                if (isConnected[i][j] && uf.isConnected(i, j) == false) {
                    ans--;
                    uf.unionSet(i, j);
                }
            }
        }
        return ans;
    }
};

## Solution 2 - DFS
#### Python

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

        for i in range(n):
            if i in seen:
                continue
            res += 1
            
            q = deque([i])
            seen.add(i)
            
            while q:
                cur = q.pop()
                
                for nei in range(n):
                    if isConnected[cur][nei] and nei not in seen:
                        q.append(nei)
                        seen.add(nei)

        return res

#### C++

class Solution {
public:
    void dfs(vector<vector<int>>& isConnected, vector<int>& seen, int i) {
        seen[i] = 1;
        for (int j = 0; j < isConnected.size(); j++) {
            if (i != j && isConnected[i][j] == 1 && seen[j] == 0) {
                dfs(isConnected, seen, j);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<int> seen(n, 0);

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (seen[i] == 0) {
                ans++;
                dfs(isConnected, seen, i);
            }
        }
        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O(n) |
>| Solution 2 | O($n^2$) | O(n) |

## Note
x