Leetcode 1971 - Find if Path Exists in Graph

題目

Problem#

給你一個雙向圖有 $n$ 個點 $m$ 條邊，從 $0$ 到 $n-1$，問你能不能從 src 走到 dst

• $1 \le n \le 2e5$
• $0 \le m \le 2e5$
• 沒有重複的邊 or 自環

想法#

disjoint set $\approx \mathcal{O}(1)$

• 時間複雜度: $\mathcal{O}(m)$ m = number of edges
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

• disjoint set

Copy

#define N 200000
struct Disjoint
{
    int p[N+5];
    void init(int n)
    {
        for(int i = 0; i <= n; i++)
            p[i] = i;
    }
    int find(int x)
    {
        return (p[x]==x) ? x : (p[x] = find(p[x]));
    }
    void uni(int a, int b)
    {
        p[find(a)] = find(b);
    }
};
 
class Solution {
public:
    Disjoint set;
    bool validPath(int n, vector<vector<int>>& edges, int src, int dst)
    {
        set.init(n);
        for(auto i : edges)
        {
            auto &&[a, b] = tie(i[0], i[1]);
            set.uni(a, b);
        }
        // printf("> %d %d\n", set.find(src), set.find(dst));
        return set.find(src) == set.find(dst);
    }
};

view raw leetcode/1971.cpp delivered with ❤ by emgithub

• DFS

Copy

// DFS
class Solution2 {
public:
    vector<int> G[N+5];
    bool vis[N+5];
    bool ans = false;
 
    void dfs(int s, int d)
    {
        //printf("> %d %d\n", s, d);
        // vis[s] = true;
 
        if(s == d)
        {
            ans = true;
            return;
        }
 
        for(int i : G[s])
        {
            if(!vis[i])
            {
                vis[i] = true;
                dfs(i, d);
                // vis[i] = false; TLE!
            }
        }
        // vis[s] = false;
    }
 
    bool validPath(int n, vector<vector<int>>& e, int src, int dst)
    {
        // build
        for(auto &i : e)
        {
            auto &&[a, b] = tie(i[0], i[1]);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        memset(vis, 0, sizeof(vis));
        vis[src] = true;
        dfs(src, dst);
        return ans;
    }
};

view raw leetcode/1971.cpp delivered with ❤ by emgithub

賞析#

https://haogroot.com/2021/01/29/union_find-leetcode/
https://zh.wikipedia.org/zh-tw/并查集
https://hackmd.io/SSUEUC2_SWW6CBPvgT6yiA
https://leetcode.com/problems/find-if-path-exists-in-graph/solutions/2715942/find-if-path-exists-in-graph/

心得#

太久沒有寫 disjoint set 直接忘記了= =