LeetCode Entry

1971. Find if Path Exists in Graph

21.04.2024 easy 2024 kotlin rust

Are source and destination connected in graph?

1971. Find if Path Exists in Graph easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/578

Problem TLDR

Are source and destination connected in graph? #easy

Intuition

Let’s check connected components with Union-Find data structure https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Approach

We can use a HashMap or just simple array. To optimize Union-Find root function, we can use path compression step. There are other tricks (https://arxiv.org/pdf/1911.06347.pdf), but let’s keep code shorter.

Complexity

• Time complexity: \(O(E + V)\), V = n, E = edges.size, assuming root is constant for inverse Ackermann function (https://codeforces.com/blog/entry/98275) (however only with all the tricks implemented, like ranks and path compressing https://cp-algorithms.com/data_structures/disjoint_set_union.html)

• Space complexity: \(O(V)\)

Code

    fun validPath(n: Int, edges: Array<IntArray>, source: Int, destination: Int): Boolean {
        val uf = IntArray(n) { it }
        fun root(a: Int): Int { var x = a; while (x != uf[x]) x = uf[x]; uf[a] = x; return x }
        for ((a, b) in edges) uf[root(a)] = root(b)
        return root(source) == root(destination)
    }

    pub fn valid_path(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
        let mut uf = (0..n as usize).collect();
        fn root(uf: &mut Vec<usize>, a: i32) -> usize {
            let mut x = a as usize; while x != uf[x] { x = uf[x] }; uf[a as usize] = x; x
        }
        for ab in edges { let a = root(&mut uf, ab[0]); uf[a] = root(&mut uf, ab[1]) }
        root(&mut uf, source) == root(&mut uf, destination)
    }