Re: [閒聊] 每日leetcode

[oinishere (是oin捏)]

※ 引述 《Rushia (早瀬ユウカの体操服)》 之銘言：
: 　
: https://leetcode.com/problems/find-if-path-exists-in-graph/description
: 1971. Find if Path Exists in Graph
: 給你一個陣列表示的圖，判斷 source 和 destination 是否連通。
: 　
: 思路:
: 1.把所有邊的點加到併查集，然後查這兩點有沒有連通就好。



思路解法:
用dp+bfs
我記得這樣好像算是dijk甚麼東西的
反正就是要一直看走過的地方能到哪裡

然後我runtime 超久 靠北

我要去看優化了


```cpp
class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destinatio
n)
    {

        int elen = edges.size();

        unordered_map<int,vector<int>> paper;

        for(int i = 0 ; i < elen ; i ++)
        {
            paper[edges[i][0]].push_back(edges[i][1]);
            paper[edges[i][1]].push_back(edges[i][0]);
        }

        vector<int> place(n , 0);
        vector<int> placeb(n , 0);

        place[source] = 1;

        int ok = 1;
        while(ok)
        {
            placeb = place;
            ok = 0;

            for(int i = 0 ; i < n ; i ++)
            {
                if(place[i] == 0)continue;

                for(int k : paper[i])
                {
                    if(k == destination)return true;
                    if(place[k] == 0)
                    {
                        placeb[k] = 1;
                        ok = 1;
                    }
                }
                paper.erase(i);
            }

            place = placeb;


        }

        if(place[destination])return true;
        return false;

    }
};
```


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.34.62 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713676137.A.E3A.html
→ digua: 大師
推 JIWP: 大師
推 SecondRun: 大師