Description

Submission

class Solution {
    vector<vector<int>> graph;
    vector<int> visited;
    int ret;

    bool dfs(int n) {
        if(visited[n]) return false;
        visited[n] = 1;

        for(auto x: graph[n]) {
            dfs(x);
        }

        return true;
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        graph.resize(n);
        visited.resize(n, 0);
        ret = 0;

        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                if(!isConnected[i][j]) continue;
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }

        for(int i = 0; i < n; ++i) {
            if(dfs(i)) ++ret;
        }

        return ret;
    }
};

class Solution {
    vector<int> arr;

    void ufUnion(int a, int b) {
        int x = ufFind(a);
        int y = ufFind(b);
        arr[x] = y;
    }

    int ufFind(int a) {
        if(a == arr[a]) return a;
        return arr[a] = ufFind(arr[a]);
    }

    void ufInit(int n) {
        arr.resize(n);
        for(int i = 0; i < n; ++i) {
            arr[i] = i;
        }
    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        arr.resize(n);
        ufInit(n);

        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                if(isConnected[i][j]) ufUnion(i, j);
            }
        }
        
        set<int> st;
        for(int i = 0; i < n; ++i) {
            st.insert(ufFind(i));
        }

        return st.size();
    }
};