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

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

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png" style="width: 141px; height: 121px;" />
<pre>
<strong>Input:</strong> n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
<strong>Output:</strong> true
<strong>Explanation:</strong> There are two paths from vertex 0 to vertex 2:
- 0 &rarr; 1 &rarr; 2
- 0 &rarr; 2
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png" style="width: 281px; height: 141px;" />
<pre>
<strong>Input:</strong> n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
<strong>Output:</strong> false
<strong>Explanation:</strong> There is no path from vertex 0 to vertex 5.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>0 &lt;= edges.length &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
	<li><code>0 &lt;= source, destination &lt;= n - 1</code></li>
	<li>There are no duplicate edges.</li>
	<li>There are no self edges.</li>
</ul>

class DisjointSet {
public:
    DisjointSet(int n) : ds(n) {
        for (int i = 0; i < n; i++) {
            ds[i] = -1;
        }
    }

    int find(int i) {
        if (ds[i] < 0) {
            return i;
        }

        return find(ds[i]);
    }

    void unionBySize(int x, int y) {
        // cout << ds[root1] << endl;
        int root1 = find(x);
        int root2 = find(y);
        // int newSize = ds[root1] + ds[root2];

        if (root1 != root2) {
            int newSize = ds[root1] + ds[root2];
        if (ds[root1] < ds[root2]) {
            ds[root2] = root1;
            ds[root1] = newSize;
        } else {
            ds[root1] = root2;
            ds[root2] = newSize;
        } 
        }
    }

private:
    vector<int> ds;
};

class Solution {
public:
    unordered_map<int, vector<int>> adj;

    bool dfs(int source, int dest, vector<bool>& visited) {
        if (source == dest) {
            return true;
        }

        // if (!visited[source]) {
        //     visited[source] = true;

        //     for (const auto& neighbor : adj[source]) {
        //         if (dfs(neighbor, dest, visited)) {
        //             return true;
        //         }
        //     }
        // }

        for (const auto& neighbor : adj[source]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;

                if (dfs(neighbor, dest, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    bool bfs(int source, int dest, vector<bool>& visited) {
        // queue<int> todo;
        stack<int> todo;

        todo.push(source);
        visited[source] = true;

        while (!todo.empty()) {
            // int curr = todo.front();
            int curr = todo.top();
            todo.pop();

            if (curr == dest) {
                return true;
            }

            // for all neighbors of current node, if not visited,
            // add it to the queue and mark it as visited
            for (const int& neighbor : adj[curr]) {
                if (!visited[neighbor]) {
                    todo.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }

        return false;
    }
    
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        // T: O(n + m), S: O(n + m)
        DisjointSet s(n);

        for (const auto& edge : edges) {
            cout << s.find(edge[0]) << endl;
            s.unionBySize(edge[0], edge[1]);
        }

        return s.find(source) == s.find(destination);

        vector<bool> visited(n, false);

        // build adjacency list
        for (const auto& edge : edges) {
            int from = edge[0];
            int to = edge[1];
            adj[from].push_back(to);
            adj[to].push_back(from);
        }

        // return bfs(source, destination, visited);
        // return dfs(source, destination, visited);
    }
};
205367