Find if Path Exists in Graph

🏠 ⬅️ ➡️

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] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. 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 * 105
  • 0 <= edges.length <= 2 * 105
  • edges[i].length == 2
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 0 <= source, destination <= n - 1
  • There are no duplicate edges.
  • There are no self edges.
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    integer, parameter :: edges(n, n) = reshape([&
        & 0, 1, 2, &
        & 1, 2, 0, &
        & 2, 0, 1], shape(edges))
    integer, parameter :: source = 0
    integer, parameter :: destination = 2

    write(*, '(L1)') validPath(edges, n, source, destination)

contains

    function validPath(edges, n, source, destination) result(valid)
        implicit none
        integer, intent(in) :: n
        integer, intent(in) :: edges(:, :)
        integer, intent(in) :: source
        integer, intent(in) :: destination
        logical :: valid
        integer :: i, j

        valid = .false.

        do i = 0, n - 1
            do j = 0, n - 1
                if (edges(i, j) == 1) then
                    if (i == source .and. j == destination) then
                        valid = .true.
                    end if
                end if
            end do
        end do
    end function validPath
end program main
❌ Compiled
❌ Executed
❌ Correct 
module BidirectionalGraph
    implicit none
    private
    public :: has_path

contains

    logical function has_path(n, edges, source, destination) result(has_path)
        integer, intent(in) :: n
        integer, intent(in) :: edges(:, :)
        integer, intent(in) :: source
        integer, intent(in) :: destination
        integer :: i, j, k
        logical :: visited(n)
        integer :: parent(n)

        has_path = .false.

        ! Initialize visited and parent arrays
        visited = .false.
        parent = -1

        ! Set source vertex as visited and parent to -1
        visited(source) = .true.
        parent(source) = -1

        ! Perform BFS from source vertex
        call bfs(n, edges, source, visited, parent)

        ! Check if destination vertex is visited
        if (visited(destination)) then
            ! Find path from source to destination
            k = destination
            do while (k /= -1)
                write (*, *) k
                k = parent(k)
            end do
            has_path = .true.
        end if

    contains

        ! Breadth-First Search (BFS)
        subroutine bfs(n, edges, source, visited, parent)
            integer, intent(in) :: n
            integer, intent(in) :: edges(:, :)
            integer, intent(in) :: source
            logical, intent(inout) :: visited(n)
            integer, intent(inout) :: parent(n)
            integer :: i, j, k
            integer :: queue(n)
            integer :: front, rear

            ! Initialize queue and counters
            front = 1
            rear = 0
            queue(1) = source

            ! Loop until queue is empty
            do while (front <= rear)
                ! Dequeue vertex and mark as visited
                k = queue(front)
                front = front + 1
                visited(k) = .true.

                ! Loop through neighbors of dequeued vertex
                do i = 1, n
                    j = edges(k, i)
                    if (.not. visited(j)) then
                        ! Enqueue neighbor and set parent
                        rear = rear + 1
                        queue(rear) = j
                        parent(j) = k
                    end if
                end do
            end do

        end subroutine bfs

    end function has_path
end module BidirectionalGraph

! Test program
program test
    use BidirectionalGraph
    implicit none
    integer :: n, source, destination
    integer, allocatable :: edges(:, :)
    logical :: has_path

    ! Test case 1
    n = 3
    allocate(edges(n, n))
    edges = reshape([0, 1, 1, 2, 2, 0], shape(edges))
    source = 0
    destination = 2
    has_path = has_path(n, edges, source, destination)
    if (has_path) then
        write (*, *) "Valid path exists from", source, "to", destination
    else
        write (*, *) "No valid path exists from", source, "to", destination
    end if

    ! Test case 2
    n = 6
    allocate(edges(n, n))
    edges = reshape([0, 1, 0, 2, 1, 3, 2, 4, 3, 5, 4, 5, 0], shape(edges))
    source = 0
    destination = 5
    has_path = has_path(n, edges, source, destination)
    if (has_path) then
        write (*, *) "Valid path exists from", source, "to", destination
    else
        write (*, *) "No valid path exists from", source, "to", destination
    end if

    ! Test case 3
    n = 7
    allocate(edges(n, n))
    edges = reshape([0, 1, 0, 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 6,
🌐 Data from online sources 
def mem_sticks_crash(memory1, memory2):
    crash_time = 1
    while True:
        if memory1 >= memory2:
            if memory1 >= crash_time:
                memory1 -= crash_time
            else:
                break
        else:
            if memory2 >= crash_time:
                memory2 -= crash_time
            else:
                break
        crash_time += 1
    return [crash_time, memory1, memory2]

The algorithm starts with a crashTime counter initialized to 1. Then we enter an infinite loop where we compare the available memory on both sticks. If the memory of stick 1 is greater or equal to stick 2, we try to allocate crashTime bits to it, but only if it has enough bits. If it doesn't have enough bits, we break the loop; otherwise, we subtract the bits used from it. We do the same for the memory stick with the lesser memory. Finally, we increment the crashTime counter by 1 at each iteration. When the loop breaks, the function returns an array containing crashTime, and the memory states of both memory sticks at the time of the crash. The algorithm is the same for all languages, with only minimal syntax adjustments.

🌐 Data from online sources 
#include <vector>

std::vector<int> memSticksCrash(int memory1, int memory2) {
    int crashTime = 1;
    while (true) {
        if (memory1 >= memory2) {
            if (memory1 >= crashTime) {
                memory1 -= crashTime;
            } else {
                break;
            }
        } else {
            if (memory2 >= crashTime) {
                memory2 -= crashTime;
            } else {
                break;
            }
        }
        crashTime++;
    }
    return {crashTime, memory1, memory2};
}

The algorithm starts with a crashTime counter initialized to 1. Then we enter an infinite loop where we compare the available memory on both sticks. If the memory of stick 1 is greater or equal to stick 2, we try to allocate crashTime bits to it, but only if it has enough bits. If it doesn't have enough bits, we break the loop; otherwise, we subtract the bits used from it. We do the same for the memory stick with the lesser memory. Finally, we increment the crashTime counter by 1 at each iteration. When the loop breaks, the function returns an array containing crashTime, and the memory states of both memory sticks at the time of the crash. The algorithm is the same for all languages, with only minimal syntax adjustments.