commit ed4e37d10c3dbc466b1d3914f5dfc5cfdcf5f7d9
parent 76e6c84f4d1f40b5982d9b626c1d592e735e49db
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 4 Jan 2023 23:56:02 +0100
Some graph problems
- Union_Find.cpp
* Union by size instead of rank, useful for some problems
Diffstat:
6 files changed, 202 insertions(+), 7 deletions(-)
diff --git a/Problems/0851.cpp b/Problems/0851.cpp
@@ -0,0 +1,29 @@
+class Solution {
+public:
+ vector<int> loudAndRich(vector<vector<int>> &richer, vector<int> &quiet) {
+ const int n = quiet.size();
+ vector<vector<int>> adj(n);
+ vector<int> count(n);
+ vector<int> res(n);
+ iota(res.begin(), res.end(), 0);
+
+ for (auto &p : richer) {
+ adj[p[0]].push_back(p[1]);
+ count[p[1]]++;
+ }
+
+ queue<int> q;
+ for (int i = 0; i < n; i++)
+ if (!count[i]) q.push(i);
+
+ while (!q.empty()) {
+ int crnt = q.front();
+ q.pop();
+ for (int &c : adj[crnt]) {
+ if (quiet[res[c]] > quiet[res[crnt]]) res[c] = res[crnt];
+ if (!--count[c]) q.push(c);
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/1462.cpp b/Problems/1462.cpp
@@ -0,0 +1,103 @@
+// DFS
+class Solution {
+public:
+ vector<bool> checkIfPrerequisite(int numCourses,
+ vector<vector<int>> &prerequisites,
+ vector<vector<int>> &queries) {
+ vector<vector<int>> adj(numCourses);
+ vector<unordered_set<int>> pre(numCourses);
+
+ for (auto &p : prerequisites) adj[p[0]].push_back(p[1]);
+
+ for (int i = 0; i < numCourses; i++) {
+ unordered_set<int> visited;
+ stack<int> st;
+ st.push(i);
+ visited.insert(i);
+ while (!st.empty()) {
+ int crnt = st.top();
+ st.pop();
+ for (int &c : adj[crnt]) {
+ if (visited.count(c)) continue;
+ visited.insert(c);
+ pre[c].insert(i);
+ st.push(c);
+ }
+ }
+ }
+
+ vector<bool> res;
+ for (auto &p : queries) res.push_back(pre[p[1]].count(p[0]));
+ return res;
+ }
+};
+
+// Topological sort with dependency propagation
+class Solution {
+public:
+ vector<bool> checkIfPrerequisite(int numCourses,
+ vector<vector<int>> &prerequisites,
+ vector<vector<int>> &queries) {
+ vector<unordered_set<int>> pre(numCourses);
+ vector<vector<int>> adj(numCourses);
+ vector<int> count(numCourses);
+
+ for (auto &p : prerequisites) {
+ adj[p[0]].push_back(p[1]);
+ count[p[1]]++;
+ }
+
+ queue<int> q;
+ for (int i = 0; i < numCourses; i++)
+ if (!count[i]) q.push(i);
+
+ while (!q.empty()) {
+ int crnt = q.front();
+ q.pop();
+ for (int &c : adj[crnt]) {
+ pre[c].insert(crnt);
+ pre[c].insert(pre[crnt].begin(), pre[crnt].end());
+ if (!--count[c]) q.push(c);
+ }
+ }
+
+ vector<bool> res;
+ for (auto &p : queries) res.push_back(pre[p[1]].count(p[0]));
+ return res;
+ }
+};
+
+// Topological sort using bitseclass Solution {
+public:
+vector<bool> checkIfPrerequisite(int numCourses,
+ vector<vector<int>> &prerequisites,
+ vector<vector<int>> &queries) {
+ vector<bitset<100>> pre(numCourses);
+ vector<vector<int>> adj(numCourses);
+ vector<int> count(numCourses);
+
+ for (auto &p : prerequisites) {
+ adj[p[0]].push_back(p[1]);
+ count[p[1]]++;
+ }
+
+ queue<int> q;
+ for (int i = 0; i < numCourses; i++)
+ if (!count[i]) q.push(i);
+
+ while (!q.empty()) {
+ int crnt = q.front();
+ q.pop();
+ for (int &c : adj[crnt]) {
+ pre[c].set(crnt);
+ pre[c] |= pre[crnt];
+ if (!--count[c]) q.push(c);
+ }
+ }
+
+ vector<bool> res;
+ for (auto &p : queries) res.push_back(pre[p[1]][p[0]]);
+ return res;
+}
+}
+;
diff --git a/Problems/2244.cpp b/Problems/2244.cpp
@@ -0,0 +1,14 @@
+class Solution {
+public:
+ int minimumRounds(vector<int> &tasks) {
+ unordered_map<int, int> um;
+ for (int t : tasks) um[t]++;
+
+ int round = 0;
+ for (auto [_, c] : um) {
+ if (c == 1) return -1;
+ round += (c - 1) / 3 + 1;
+ }
+ return round;
+ }
+};
diff --git a/Problems/2316.cpp b/Problems/2316.cpp
@@ -0,0 +1,45 @@
+class UnionFind {
+ int n, cnt = n;
+ vector<int> root, size;
+
+public:
+ UnionFind(int n) : n(n), root(n), size(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 (size[x] > size[y]) swap(x, y);
+ root[x] = y;
+ size[y] += size[x];
+ cnt--;
+ }
+ }
+
+ int count() { return cnt; }
+ bool connected(int x, int y) { return find(x) == find(y); }
+
+ long long count_unreachable() {
+ long long res = 0;
+
+ for (int i = 0; i < n; i++)
+ if (root[i] == i) res += (long long)size[i] * (n - size[i]);
+
+ return res / 2;
+ }
+};
+
+class Solution {
+public:
+ long long countPairs(int n, vector<vector<int>> &edges) {
+ UnionFind uf(n);
+ for (auto &e : edges) uf.join(e[0], e[1]);
+ return uf.count_unreachable();
+ }
+};
diff --git a/README.md b/README.md
@@ -182,6 +182,7 @@ for solving problems.
| 0830 | Medium | [Kth Smallest Element in a BST](Problems/0230.cpp) |
| 0841 | Medium | [Keys and Rooms](Problems/0841.cpp) |
| 0844 | Easy | [Backspace String Compare](Problems/0844.cpp) |
+| 0851 | Medium | [Loud and Rich](Problems/0851.cpp) |
| 0872 | Easy | [Leaf-Similar Trees](Problems/0872.cpp) |
| 0876 | Easy | [Middle of the Linked List](Problems/0876.cpp) |
| 0886 | Medium | [Possible Bipartition](Problems/0886.cpp) |
@@ -235,6 +236,7 @@ for solving problems.
| 1382 | Medium | [Balance a Binary Search Tree](Problems/1382.cpp) |
| 1425 | Hard | [Constrained Subsequence Sum](Problems/1425.cpp) |
| 1438 | Medium | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/0143.cpp) |
+| 1462 | Medium | [Course Schedule IV](Problems/1462.cpp) |
| 1466 | Medium | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp) |
| 1472 | Medium | [Design Browser History ](Problems/1472.cpp) |
| 1480 | Easy | [Running Sum of 1d Array](Problems/1480.cpp) |
@@ -270,9 +272,11 @@ for solving problems.
| 2192 | Medium | [All Ancestors of a Node in a Directed Acyclic Graph](Problems/2192.cpp) |
| 2235 | Easy | [Add Two Integers](Problems/2235.cpp) |
| 2236 | Easy | [Root Equals Sum of Children](Problems/2236.cpp) |
+| 2244 | Medium | [Minimum Rounds to Complete All Tasks](Problems/2244.cpp) |
| 2265 | Medium | [Count Nodes Equal to Average of Subtree](Problems/2265.cpp) |
| 2279 | Medium | [Maximum Bags With Full Capacity of Rocks](Problems/2279.cpp) |
| 2285 | Medium | [Maximum Total Importance of Roads](Problems/2285.cpp) |
+| 2316 | Medium | [Count Unreachable Pairs of Nodes in an Undirected Graph](Problems/2316.cpp) |
| 2326 | Medium | [Spiral Matrix IV](Problems/2326.cpp) |
| 2331 | Easy | [Evaluate Boolean Binary Tree](Problems/2331.cpp) |
| 2368 | Medium | [Reachable Nodes With Restrictions](Problems/2368.cpp) |
diff --git a/Templates/Union_Find.cpp b/Templates/Union_Find.cpp
@@ -1,9 +1,9 @@
class UnionFind {
- int n;
- vector<int> root, rank;
+ int n, cnt = n;
+ vector<int> root, size;
public:
- UnionFind(int n) : n(n), root(n), rank(n, 1) {
+ UnionFind(int n) : n(n), root(n), size(n, 1) {
iota(root.begin(), root.end(), 0);
}
@@ -15,13 +15,13 @@ public:
void join(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
- if (rank[x] > rank[y]) swap(x, y);
+ if (size[x] > size[y]) swap(x, y);
root[x] = y;
- rank[y] += 1;
- n--;
+ size[y] += size[x];
+ cnt--;
}
}
- int count() { return n; }
+ int count() { return cnt; }
bool connected(int x, int y) { return find(x) == find(y); }
};
