clueless coding // TODO: be smarter

LeetCode Number of Connected Components in an Undirected Graph: CPP Solution



TL;DR Code Solution


int countComponents(int n, vector<pair<int, int>>& edges) {
    vector<int> parents(n);
    for (int i = 0; i < parents.size(); i++) {
        parents[i] = i;
    }

    int result = n;
    for (int i = 0; i < edges.size(); i++) {
        int from = edges[i].first;
        int to = edges[i].second;
        if (findParent(parents, from) != findParent(parents, to)) {
            parents[findParent(parents, from)] = to;
            result--;
        }
    }

    return result;
}

int findParent(vector<int>& parents, int child) {
    while (parents[child] != child) {
        child = parents[child];
    }
    return child;
}