并查集 两个顶点之间是否存在路径pta数据结构

可以使用并查集来判断两个顶点之间是否存在路径。

具体实现方法如下：

1. 初始化并查集，将每个顶点都单独成为一个集合，集合代表该顶点所在的连通块。

2. 遍历所有的边，将边连接的两个顶点所在的集合合并。

3. 判断两个顶点是否在同一个集合中，如果在同一个集合中，则说明它们之间存在路径。

具体实现细节可以参考以下代码（假设顶点编号从0开始）：

class UnionFindSet {
public:
    UnionFindSet(int n) : parent(n), size(n) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 初始化每个顶点所在的集合
        }
    }
    
    int find(int x) { // 查找x所在的集合
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void merge(int x, int y) { // 合并x和y所在的集合
        int px = find(x), py = find(y);
        if (px != py) {
            parent[px] = py;
            size[py] += size[px];
        }
    }
    
    bool connected(int x, int y) { // 判断x和y是否在同一个集合中
        return find(x) == find(y);
    }
    
    int getSize(int x) { // 获取x所在集合的大小
        return size[find(x)];
    }
    
private:
    vector<int> parent; // parent[i]表示i的父节点
    vector<int> size; // size[i]表示i所在集合的大小
};

bool hasPath(vector<vector<int>>& graph, int src, int dst) {
    int n = graph.size();
    UnionFindSet uf(n);
    for (int i = 0; i < n; ++i) {
        for (int j : graph[i]) {
            uf.merge(i, j); // 将每条边连接的两个顶点所在的集合合并
        }
    }
    return uf.connected(src, dst); // 判断src和dst是否在同一个集合中
}

其中，`parent`数组表示每个顶点的父节点，`size`数组表示每个集合的大小。`find()`函数用于查找某个顶点所在的集合，`merge()`函数用于合并两个集合，`connected()`函数用于判断两个顶点是否在同一个集合中，`getSize()`函数用于获取某个顶点所在集合的大小。最后，`hasPath()`函数用于判断两个顶点之间是否存在路径。