LeetCode 547. Number of Provinces

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        const int N = M.size();
        vector<bool> visited(N, false);
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            if (!visited[i]) {
                ++cnt;
                dfs(M, i, visited);
            }
        return cnt;
    }
private:
    void dfs(vector<vector<int>>& M, int i, vector<bool>& visited) {
        visited[i] = true;
        for (int j = 0; j < M.size(); ++j)
            if (M[i][j] && !visited[j])
                dfs(M, j, visited);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        const int N = M.size();
        vector<bool> visited(N, false);
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            if (!visited[i]) {
                ++cnt;
                dfs(M, i, visited);
            }
        return cnt;
    }
private:
    void dfs(vector<vector<int>>& M, int i, vector<bool>& visited) {
        visited[i] = true;
        for (int j = 0; j < M.size(); ++j)
            if (M[i][j] && !visited[j])
                dfs(M, j, visited);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        const int N = M.size();
        for (int i = 0; i < N; ++i)
            f.push_back(i);
        for (int i = 0; i < N; ++i)
            for (int j = i + 1; j < N; ++j)
                if (M[i][j])
                    _union(i, j);
        int cnt = 0;
        for (int i = 0; i < N; ++i)
            if (f[i] == i)
                ++cnt;
        return cnt;
    }
private:
    vector<int> f;
    int find(int i) {
        int j = i;
        while (f[i] != i)
            i = f[i];
        while (j != i) {
            int next = f[j];
            f[j] = i;
            j = next;
        }
        return i;
    }
    void _union(int i, int j) {
        f[find(i)] = find(j);
    }
};