Re: [閒聊] 每日LeetCode已回收
2421. Number of Good Paths
這題我很有印象
是我參加的第二場的周賽的最後一題
也是我第一個沒寫出來的周賽題
所以已經寫過一次了
不過當初的文已經被砍了
這題是圖論的 connectivity 問題
可以用 union find 做（又是 union find！）
如果我們想要找出所有頭尾的值是 p 的 good path
對任意 u, v 且 vals[u] = vals[v] = p 而言
這兩點之間存在 good path 等價於：
在只考慮那些兩端的值都 <= p 的邊時這兩點是否連通
是否連通用 union find 就可
把有同樣 parent 的點收集起來
他們之間的配對有 C n 取 2 種
還要包含單獨一個點的 path
因為樹上任兩點恰有一條路徑
所以只要算有多少 u, v 之間存在 good path 即可
---------------------------------------------
class Solution {
public:
struct UnionFind {
vector<int> parent;
vector<int> rank;
UnionFind(int n) {
parent = vector<int>(n);
rank = vector<int>(n);
iota(parent.begin(), parent.end(), 0);
}
int find(int a) {
if (parent[a] != a)
parent[a] = find(parent[a]);
return parent[a];
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (rank[u] < rank[v])
swap(u, v);
parent[v] = u;
if (rank[u] == rank[v])
rank[u] += 1;
}
};
struct G { // graph
vector<int> V;
vector<pair<int, int>> E;
};
int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
int n = vals.size();
UnionFind uf(n);
map<int, G> subGraphs; // val --> subgraph
for (int i = 0; i < n; i++)
subGraphs[vals[i]].V.push_back(i);
for (auto& e: edges) {
int u = e[0], v = e[1];
int val = max(vals[u], vals[v]);
subGraphs[val].E.push_back({u, v});
}
int ans = 0;
for (auto [_, subG]: subGraphs) {
auto& [subV, subE] = subG;
for (auto [u, v]: subE)
uf.merge(u, v);
unordered_map<int, int> group;
for (int idx: subV)
group[uf.find(idx)] += 1;
for (auto [_, num]: group)
ans += num * (num + 1) / 2;
}
return ans;
}
};
---------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673748567.A.263.html
推
01/15 10:11,
2年前
, 1F
01/15 10:11, 1F
推
01/15 10:35,
2年前
, 2F
01/15 10:35, 2F
→
01/15 10:37,
2年前
, 3F
01/15 10:37, 3F
討論串 (同標題文章)
完整討論串 (本文為第 194 之 719 篇)：