<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 Solution {
 public:
	struct Graph
	{
		Graph(int numVertices)
			: m_adjacencyList(numVertices)
			, m_parents(numVertices)
		{
			for(int i=0; i < numVertices; ++i)
			{
				m_parents[i] = i;
			}
		}

		void AddEdge(int source, int destination, bool bidirectional = true)
		{
			m_adjacencyList[source].push_back(destination);
			if (bidirectional)
			{
				m_adjacencyList[destination].push_back(source);
			}
			Union(source, destination);
		}

		bool isConnected(int source, int destination)
		{
			auto parent1 = Find(source);
			auto parent2 = Find(destination);

			return parent1 == parent2;
		}

		int Find(int vertex)
		{
			if (vertex == m_parents[vertex])
			{
				return vertex;
			}

			return m_parents[vertex] = Find(m_parents[vertex]);
		}

		void Union(int source, int destination)
		{
			int sourceParent = Find(source);
			int destinationParent = Find(destination);

			if(sourceParent!= destinationParent)
			{
				m_parents[sourceParent] = destinationParent;
			}
		}

		bool Dfs(int vertex, int target, std::vector<bool>& visited)
		{
			if (vertex == target)
			{
                return true;
			}

			visited[vertex] = true;

            for(const auto& neighbor : m_adjacencyList[vertex])
            {
                if (!visited[neighbor])
                {
                    if (Dfs(neighbor, target, visited))
                    {
                        return true;
                    }
                }
            }

            return false;
		}

	 private:
		std::vector<std::vector<int>> m_adjacencyList;
		std::vector<int> m_parents;
	};

	bool validPath(int n, vector<vector<int>>& edges, int source, int destination)
	{
		Graph graph(n);

        for(const auto& edge : edges)
        {
            graph.AddEdge(edge[0], edge[1]);
        }

		std::vector<bool> visited(n, false);
		return graph.Dfs(source, destination,visited);

        //return graph.isConnected(source, destination);
	}
};

353307