algo-aha

连通子图的个数

• https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

int countComponents(int n, vector<pair<int, int>>& edges) {
    // 并查集
    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    
    // unite
    for (auto &edge : edges) {
        int x = find(edge.first, parent);
        int y = find(edge.second, parent);
        if (x != y) {
            parent[x] = y;
            n--;
        }
    }
    return n;
}

int find(int x, vector<int> &parent) {
    if (parent[x] != x) 
        parent[x] = find(parent[x], parent);
    return parent[x];
}

冗余的连接

• https://leetcode.com/problems/redundant-connection/

vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    // 并查集
    const int N = edges.size(); // 已知节点数N为输入数组长
    vector<int> parent(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
    // unite
    for (auto &edge : edges) {
        int pu = find(edge[0], parent);
        int pv = find(edge[1], parent);
        if (pu == pv) return edge;
        parent[pu] = pv;
    }
    return {};
}

int find(int x, vector<int> &parent) {
    if (parent[x] != x) {
        parent[x] = find(parent[x], parent);
    }
    return parent[x];
}

最多能去掉多少石头

• https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

int removeStones(vector<vector<int>>& stones) {
    // 同行或同列的要在一个并查集，这里的技巧是，
    // 把行或列作为某种资源点，石头位置连接了行列资源点，
    // 将列j+10000以区别于行i资源点
    unordered_map<int, int> uf;
    int islands = 0;
    for (auto &stone : stones) {
        unite(stone[0], stone[1] + 10000, uf, islands);
    }
    return stones.size() - islands;
}

int find(int x, unordered_map<int, int> &uf, int &islands) {
    if (!uf.count(x)) {
        uf[x] = x;
        islands++;
    }

    if (uf[x] != x) uf[x] = find(uf[x], uf, islands);
    return uf[x];
}

void unite(int x, int y, unordered_map<int, int> &uf, int &islands) {
    int px = find(x, uf, islands), py = find(y, uf, islands);
    if (px != py) {
        uf[py] = px;
        islands--;
    }
}