commit fc752a9fdb9fc285e98d4b11810af07996c6e0da
parent cb8c0714d657254df7e7eaa6653407d969920bf9
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Tue, 3 Jan 2023 19:28:24 +0100
MST Templates, some graph problems
Diffstat:
7 files changed, 148 insertions(+), 36 deletions(-)
diff --git a/Problems/0743.cpp b/Problems/0743.cpp
@@ -1,29 +1,24 @@
class Solution {
- struct edge {
- int dest, time;
- edge(int dest, int time) : dest(dest), time(time) {}
- friend bool operator<(const edge &s1, const edge &s2) {
- return s1.time > s2.time;
- }
- };
+ typedef pair<int, int> edge;
public:
int networkDelayTime(vector<vector<int>> ×, int n, int k) {
vector<vector<edge>> adj(n + 1, vector<edge>());
- for (auto &p : times) adj[p[0]].push_back({p[1], p[2]});
+ for (auto &p : times) adj[p[0]].push_back({p[2], p[1]});
- priority_queue<edge> st;
- st.push({k, 0});
+ priority_queue<edge, vector<edge>, greater<edge>> st;
unordered_set<int> us;
+
int time = 0;
+ st.push({0, k});
while (!st.empty()) {
- auto [root, t] = st.top();
+ auto [t, root] = st.top();
st.pop();
if (us.count(root)) continue;
time = t;
us.insert(root);
- for (auto &p : adj[root])
- if (!us.count(p.dest)) st.push({p.dest, t + p.time});
+ for (auto &[time, dest] : adj[root])
+ if (!us.count(dest)) st.push({t + time, dest});
}
return us.size() == n ? time : -1;
}
diff --git a/Problems/0944.cpp b/Problems/0944.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+ int minDeletionSize(vector<string> &strs) {
+ int count = 0;
+ for (int i = 0; i < strs[0].size(); i++) {
+ for (int j = 1; j < strs.size(); j++) {
+ if (strs[j][i] < strs[j - 1][i]) {
+ count++;
+ break;
+ }
+ }
+ }
+ return count;
+ }
+};
diff --git a/Problems/1489.cpp b/Problems/1489.cpp
@@ -0,0 +1,66 @@
+class UnionFind {
+ int n;
+ vector<int> root, rank;
+
+public:
+ UnionFind(int n) : n(n), root(n), rank(n, 1) {
+ iota(root.begin(), root.end(), 0);
+ }
+
+ int find(int x) {
+ while (x != root[x]) x = root[x] = root[root[x]];
+ return x;
+ }
+
+ void join(int x, int y) {
+ x = find(x), y = find(y);
+ if (x != y) {
+ if (rank[x] > rank[y]) swap(x, y);
+ root[x] = y;
+ rank[y] += 1;
+ n--;
+ }
+ }
+
+ int count() { return n; }
+ bool connected(int x, int y) { return find(x) == find(y); }
+};
+
+class Solution {
+ typedef vector<int> edge;
+
+ int get_mst(int n, const vector<edge> &edges, int blockedge,
+ int pre_edge = -1) {
+ UnionFind uf(n);
+ int weight = 0;
+ if (pre_edge != -1) {
+ weight += edges[pre_edge][2];
+ uf.join(edges[pre_edge][0], edges[pre_edge][1]);
+ }
+ for (int i = 0; i < edges.size() && uf.count() != 1; ++i) {}
+ if (i == blockedge) continue;
+ const auto &e = edges[i];
+ if (uf.connected(e[0], e[1])) continue;
+ uf.join(e[0], e[1]);
+ weight += e[2];
+ }
+
+ return uf.count() == 1 ? weight : 1e9 + 7;
+} public : vector<vector<int>>
+ findCriticalAndPseudoCriticalEdges(int n, vector<edge> &edges) {
+ for (int i = 0; i < edges.size(); i++) edges[i].push_back(i);
+ sort(edges.begin(), edges.end(),
+ [](const edge &a, const edge &b) { return a[2] < b[2]; });
+ int origin_mst = get_mst(n, edges, -1);
+
+ vector<int> critical, non_critical;
+ for (int i = 0; i < edges.size(); i++) {
+ if (origin_mst < get_mst(n, edges, i))
+ critical.push_back(edges[i][3]);
+ else if (origin_mst == get_mst(n, edges, -1, i))
+ non_critical.push_back(edges[i][3]);
+ }
+ return {critical, non_critical};
+}
+}
+;
diff --git a/Problems/1584.cpp b/Problems/1584.cpp
@@ -1,8 +1,11 @@
class UnionFind {
+ int n;
vector<int> root, rank;
public:
- UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }
+ UnionFind(int n) : n(n), root(n), rank(n, 1) {
+ iota(root.begin(), root.end(), 0);
+ }
int find(int x) {
while (x != root[x]) x = root[x] = root[root[x]];
@@ -11,47 +14,43 @@ public:
void join(int x, int y) {
x = find(x), y = find(y);
-
if (x != y) {
if (rank[x] > rank[y]) swap(x, y);
-
root[x] = y;
- rank[y] += rank[x];
+ rank[y] += 1;
+ n--;
}
}
-};
-struct edge {
- int p1, p2;
- int cost;
- edge(int p1 = -1, int p2 = -1, int cost = INT_MAX)
- : p1(p1), p2(p2), cost(cost) {}
- bool operator()(const edge &e1, const edge &e2) { return e1.cost > e2.cost; }
+ int count() { return n; }
+ bool connected(int x, int y) { return find(x) == find(y); }
};
class Solution {
- int distance(vector<int> &p1, vector<int> &p2) {
+ typedef array<int, 3> edge;
+ typedef vector<int> point;
+
+ int distance(const point &p1, const point &p2) {
return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]);
}
public:
int minCostConnectPoints(vector<vector<int>> &points) {
- UnionFind uf(points.size() * (points.size() + 1) / 2);
- priority_queue<edge, vector<edge>, edge> pq;
+ auto cmp = [](const edge &a, const edge &b) { return a[2] > b[2]; };
+ priority_queue<edge, vector<edge>, decltype(cmp)> pq(cmp);
+ UnionFind uf(points.size());
for (int i = 0; i < points.size(); i++)
for (int j = i + 1; j < points.size(); j++)
- pq.push(edge(i, j, distance(points[i], points[j])));
+ pq.push({i, j, distance(points[i], points[j])});
- int num = 1, res = 0;
- while (num < points.size()) {
- edge e = pq.top();
+ int res = 0;
+ while (uf.count() != 1) {
+ auto [s, d, w] = pq.top();
pq.pop();
- if (uf.find(e.p1) != uf.find(e.p2)) {
- res += e.cost;
- uf.join(e.p1, e.p2);
- num++;
- }
+ if (uf.connected(s, d)) continue;
+ uf.join(s, d);
+ res += w;
}
return res;
}
diff --git a/README.md b/README.md
@@ -265,10 +265,14 @@ if you have any questions.
| 2467 | Medium | [Most Profitable Path in a Tree](Problems/2467.cpp) |
| 2477 | Medium | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
+| 0944 | Easy | [Delete Columns to Make Sorted](Problems/0944.cpp) |
+| 1489 | Hard | [Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree](Problems/1489.cpp) |
## Templates
* [Union Find](Templates/Union_Find.cpp)
+* [MST from edge vector](Templates/MST_vector.cpp)
+* [MST from edge priority queue](Templates/MST_pq.cpp)
## DNF
diff --git a/Templates/MST_pq.cpp b/Templates/MST_pq.cpp
@@ -0,0 +1,17 @@
+// Kruskal's Algorithm
+// Require UnionFind
+
+int MST(int n, priority_queue<edge> &pq) {
+ int weight = 0;
+
+ UnionFind uf(n);
+ while (!pq.empty() && uf.count() != 1) {
+ const auto &e = pq.top();
+ pq.pop();
+ if (uf.connected(e[0], e[1])) continue;
+ uf.join(e[0], e[1]);
+ weight += e[2];
+ }
+
+ return uf.count() == 1 ? weight : 1e9 + 7;
+}
diff --git a/Templates/MST_vector.cpp b/Templates/MST_vector.cpp
@@ -0,0 +1,16 @@
+// Kruskal's Algorithm
+// Require UnionFind
+
+int get_mst(int n, const vector<edge> &edges) {
+ int weight = 0;
+
+ UnionFind uf(n);
+ for (int i = 0; i < edges.size() && uf.count() != 1; i++) {
+ const auto &e = edges[i];
+ if (uf.connected(e[0], e[1])) continue;
+ uf.join(e[0], e[1]);
+ weight += e[2];
+ }
+
+ return uf.count() == 1 ? weight : 1e9 + 7;
+}
