Re: [閒聊] 每日leetcode已回收
※ 引述 《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
→
04/21 13:10,
1年前
, 1F
04/21 13:10, 1F
推
04/21 13:10,
1年前
, 2F
04/21 13:10, 2F
推
04/21 13:13,
1年前
, 3F
04/21 13:13, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 142 之 1548 篇)：