# LC 1971. Find if Path Exists in Graph

### [Problem link](https://leetcode.com/problems/find-if-path-exists-in-graph/)

###### tags: `leedcode` `easy` `c++` `Union Find`

There is a **bi-directional** graph with <code>n</code> vertices, where each vertex is labeled from <code>0</code> to <code>n - 1</code> ( **inclusive** ). The edges in the graph are represented as a 2D integer array <code>edges</code>, where each <code>edges[i] = [u_i, v_i]</code> denotes a bi-directional edge between vertex <code>u_i</code> and vertex <code>v_i</code>. Every vertex pair is connected by **at most one** edge, and no vertex has an edge to itself.

You want to determine if there is a **valid path** that exists from vertex <code>source</code> to vertex <code>destination</code>.

Given <code>edges</code> and the integers <code>n</code>, <code>source</code>, and <code>destination</code>, return <code>true</code> if there is a **valid path** from <code>source</code> to <code>destination</code>, or <code>false</code> otherwise.

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png" style="width: 141px; height: 121px;" />

Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2

**Example 2:**
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png" style="width: 281px; height: 141px;" />

Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Explanation: There is no path from vertex 0 to vertex 5.

**Constraints:**

- <code>1 <= n <= 2 * 10⁵</code>
- <code>0 <= edges.length <= 2 * 10⁵</code>
- <code>edges[i].length == 2</code>
- <code>0 <= u_i, v_i <= n - 1</code>
- <code>u_i != v_i</code>
- <code>0 <= source, destination <= n - 1</code>
- There are no duplicate edges.
- There are no self edges.

## Solution 1 - Union Find
#### C++

class UnionFind {
public:
    UnionFind(int size) : root(size), rank(size) {
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    int find(int x) {
        if (x == root[x]) {
            return x;
        }
        return root[x] = find(root[x]);
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                root[rootY] = root[rootX];
            } else if (rank[rootX] < rank[rootY]) {
                root[rootX] = root[rootY];
            } else {
                root[rootY] = root[rootX];
                rank[rootX] += 1;
            }
        }
    }

    bool isConnect(int x, int y) {
        return find(x) == find(y);
    }
private:
    vector<int> root;
    vector<int> rank;
};

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        UnionFind uf(n);
        for (vector<int>& edge: edges) {
            uf.unionSet(edge[0], edge[1]);
        }
        return uf.isConnect(source, destination);
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n) | O(n) |

## Note
x