[C++] Clean Code - DFS|UnionFind
DFS\n\nclass Solution {\npublic:\n    int findCircleNum(vector<vector<int>>& M) {\n        if (M.empty()) return 0;\n        int n = M.size();\n        vector<b
**DFS**\n```\nclass Solution {\npublic:\n    int findCircleNum(vector<vector<int>>& M) {\n        if (M.empty()) return 0;\n        int n = M.size();\n        vector<bool> visited(n, false);\n        int groups = 0;\n        for (int i = 0; i < visited.size(); i++) {\n            groups += !visited[i] ? dfs(i, M, visited), 1 : 0;\n        }\n        return groups;\n    }\n\nprivate:\n    void dfs(int i, vector<vector<int>>& M, vector<bool>& visited) {\n        visited[i] = true;\n        for (int j = 0; j < visited.size(); j++) {\n            if (i != j && M[i][j] && !visited[j]) {\n                dfs(j, M, visited);\n            }\n        }\n    }\n};\n```\n**UnionFind**\n```\nclass Solution {\npublic:\n    int findCircleNum(vector<vector<int>>& M) {\n        if (M.empty()) return 0;\n        int n = M.size();\n\n        vector<int> leads(n, 0);\n        for (int i = 0; i < n; i++) { leads[i] = i; }   // initialize leads for every kid as themselves\n\n        int groups = n;\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {   // avoid recalculate M[i][j], M[j][i]\n                if (M[i][j]) {\n                    int lead1 = find(i, leads);\n                    int lead2 = find(j, leads);\n                    if (lead1 != lead2) {       // if 2 group belongs 2 different leads, merge 2 group to 1\n                        leads[lead1] = lead2;\n                        groups--;\n                    }\n                }\n            }\n        }\n        return groups;\n    }\n\nprivate:\n    int find(int x, vector<int>& parents) {\n        return parents[x] == x ? x : find(parents[x], parents);\n    }\n};\n```
[]