From 6adb7d98bccc23cc8829611ff4b1831708932cd5 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Tue, 14 May 2024 17:01:58 +0200
Subject: add missing files

---
 datastructures/pbds.cpp             | 18 ++++++++++++++++++
 datastructures/stlPriorityQueue.cpp |  8 ++++++++
 2 files changed, 26 insertions(+)
 create mode 100644 datastructures/pbds.cpp
 create mode 100644 datastructures/stlPriorityQueue.cpp

diff --git a/datastructures/pbds.cpp b/datastructures/pbds.cpp
new file mode 100644
index 0000000..c2b44cc
--- /dev/null
+++ b/datastructures/pbds.cpp
@@ -0,0 +1,18 @@
+#include <ext/pb_ds/assoc_container.hpp>
+using namespace __gnu_pbds;
+template<typename T>
+using Tree = tree<T, null_type, less<T>, rb_tree_tag,
+                  tree_order_statistics_node_update>;
+// T.order_of_key(x): number of elements strictly less than x
+// *T.find_by_order(k): k-th element
+
+template<typename T>
+struct chash {
+	const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
+	size_t operator()(T o) const {
+		return __builtin_bswap64(hash<T>()(o) * C);
+}};
+template<typename K, typename V>
+using hashMap = gp_hash_table<K, V, chash<K>>;
+template<typename T>
+using hashSet = gp_hash_table<T, null_type, chash<T>>;
diff --git a/datastructures/stlPriorityQueue.cpp b/datastructures/stlPriorityQueue.cpp
new file mode 100644
index 0000000..32b2455
--- /dev/null
+++ b/datastructures/stlPriorityQueue.cpp
@@ -0,0 +1,8 @@
+#include <ext/pb_ds/priority_queue.hpp>
+template<typename T>
+using pQueue = __gnu_pbds::priority_queue<T>; //<T, greater<T>>
+
+auto it = pq.push(5);
+pq.modify(it, 6);
+pq.join(pq2);
+// push, join are O(1), pop, modify, erase O(log n) amortized
-- 
cgit v1.2.3


From 4680159f439b3b9651321e2dc9083a51fe6ce954 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 4 Jun 2024 15:56:33 +0200
Subject: fix havel hakimi

---
 graph/havelHakimi.cpp |   4 +++-
 graph/scc.cpp         |  15 ++++++---------
 tcr.pdf               | Bin 664992 -> 665092 bytes
 3 files changed, 9 insertions(+), 10 deletions(-)

diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp
index 6246fe0..cbd6991 100644
--- a/graph/havelHakimi.cpp
+++ b/graph/havelHakimi.cpp
@@ -1,6 +1,8 @@
 vector<vector<int>> havelHakimi(const vector<int>& deg) {
 	priority_queue<pair<int, int>> pq;
-	for (int i = 0; i < sz(deg); i++) pq.push({deg[i], i});
+	for (int i = 0; i < sz(deg); i++) {
+		if (deg[i] > 0) pq.push({deg[i], i});
+	}
 	vector<vector<int>> adj;
 	while (!pq.empty()) {
 		auto [degV, v] = pq.top(); pq.pop();
diff --git a/graph/scc.cpp b/graph/scc.cpp
index 5aa7cf2..ac9a40b 100644
--- a/graph/scc.cpp
+++ b/graph/scc.cpp
@@ -1,5 +1,5 @@
 vector<vector<int>> adj, sccs;
-int counter, sccCounter;
+int counter;
 vector<bool> inStack;
 vector<int> low, idx, s; //idx enthält Index der SCC pro Knoten.
 
@@ -14,14 +14,11 @@ void visit(int v) {
 
 	if (old == low[v]) {
 		sccs.push_back({});
-		int u;
-		do {
+		for (int u = -1; u != v;) {
 			u = s.back(); s.pop_back(); inStack[u] = false;
-			idx[u] = sccCounter;
-			sccs[sccCounter].push_back(u);
-		} while (u != v);
-		sccCounter++;
-}}
+			idx[u] = sz(sccs) - 1;
+			sccs.back().push_back(u);
+}}}
 
 void scc() {
 	inStack.assign(sz(adj), false);
@@ -29,7 +26,7 @@ void scc() {
 	idx.assign(sz(adj), -1);
 	sccs.clear();
 
-	counter = sccCounter = 0;
+	counter = 0;
 	for (int i = 0; i < sz(adj); i++) {
 		if (low[i] < 0) visit(i);
 }}
diff --git a/tcr.pdf b/tcr.pdf
index 6342868..c22d0d5 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
-- 
cgit v1.2.3