判断连通

问题描述

给你一个无向图 \(G\)，该无向图有 \(n\) 个顶点，现给你一个数组 edges，对于数组的每一个元素 edges[i] 来说，顶点 edges[i][0] 与顶点 edges[i][1] 存在边相连。

现在有一个任务，求你判断顶点 source 与顶点 destination 是否连通？

输入格式

给你一个类，需要你完善对应函数功能。

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {

    }
};

并查集给连通分量分类

并查集代码参考

class Solution {
public:
    #define vi vector<int>
    vi a, b;
    int find(int k)
    {
        if (a[k] == k) return k;
        return a[k] = find(a[k]);
    }
    void meld(int k1, int k2)
    {
        int x1 = find(k1);
        int x2 = find(k2);
        if (x1 == x2) return;
        if (b[x1] > b[x2]) a[x2] = x1;
        else if (b[x1] < b[x2]) a[x1] = x2;
        else a[x2] = x1, b[x1] ++;
    }
    bool same(int k1, int k2)
    {
        return find(k1) == find(k2);
    }
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        a = b = vi(int (2e6 + 10));
        for (int i = 0; i <= n; i ++) a[i] = i, b[i] = 1;
        for (auto x : edges)
        {
            meld(x[0], x[1]);
        }
        return same(source, destination);
    }
};