547. Number of Provinces

DFS O(n²)
n次标记，每次标记需要扫描n个city，递归深度最多为n
用这个版本

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        n = M.size();
        visited.resize(n);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                visit(M, i);
                ++res;
            }
        }
        return res;
    }

    void visit(const vector<vector<int>> &M, int u) {
        visited[u] = true;
        for (int v = 0; v < n; ++v) { // 这里必须从0开始，因为访问u的时候，小于u的并不一定已经被访问过，为了dfs把所有相关的都访问到，必须从0开始
            if (!visited[v] && M[u][v]) {
                visit(M, v);
            }
        }
    }

    int n;
    vector<bool> visited;
};

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        vector<bool> visited(n);
        int count = 0;
        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(M, i, visited);
                ++count; // 每run一次dfs就能找到一个cycle，此时update count
            }
        }
        return count;
    }

    void dfs(const vector<vector<int>> &M, int i, vector<bool> &visited) {
        for (int j = 0; j < M.size(); ++j) {
            if (M[i][j] && !visited[j]) {
                visited[j] = true;
                dfs(M, j, visited);
            }
        }
    }
};

union-find amortized O(n²)

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n = M.size();
        UF uf(n);
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (M[i][j]) {
                    uf.merge(i, j);
                }
            }
        }
        return uf.count;
    }

    struct UF {
        UF(int n) : count(n) {
            parent.resize(n);
            iota(parent.begin(), parent.end(), 0);
        }

        int getParent(int x) {
            while (parent[parent[x]] != parent[x]) {
                x = parent[x] = parent[parent[x]];
            }
            return parent[x];
        }

        void merge(int x, int y) {
            int px = getParent(x);
            int py = getParent(y);
            if (px != py) {
                parent[px] = py;
                --count;
            }
        }

        vector<int> parent;
        int count;
    };
};