1971. Find if Path Exists in Graph

Easy

There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [u_i, v_i] denotes a bi-directional edge between vertex u_i and vertex v_i. 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 source to vertex destination.

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

Example 1:

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:

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:

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

class Solution {

    public $graph;

    /**
     * @param Integer $n
     * @param Integer[][] $edges
     * @param Integer $source
     * @param Integer $destination
     * @return Boolean
     */

    public function validPath(int $n, array $edges, int $source, int $destination): bool
    {
        $this->graph = array_fill(0, $n, 0);

        for ($i = 1; $i < $n; $i++) {
            $this->graph[$i] = $i;
        }

        foreach ($edges as $edge) {
            $this->merge($this->find($edge[0]), $this->find($edge[1]));
        }

        return $this->find($this->graph[$source]) == $this->find($this->graph[$destination]);
    }

    public function find($a) {
        return $this->graph[$a] == $a ? $a : $this->graph[$a] = $this->find($this->graph[$a]);
    }

    public function merge($a, $b): void
    {
        $this->graph[$a] = $b;
    }
}

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

LinkedIn
GitHub