From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 graph/centroid.cpp | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
 create mode 100644 graph/centroid.cpp

(limited to 'graph/centroid.cpp')

diff --git a/graph/centroid.cpp b/graph/centroid.cpp
new file mode 100644
index 0000000..d2855e2
--- /dev/null
+++ b/graph/centroid.cpp
@@ -0,0 +1,22 @@
+vector<int> s;
+void dfs1(int u, int v = -1) {
+	s[u] = 1;
+	for (int w : adj[u]) {
+		if (w == v) continue;
+		dfs1(w, u);
+		s[u] += s[w];
+}}
+
+pair<int, int> dfs2(int u, int v, int n) {
+	for (int w : adj[u]) {
+		if (2 * s[w] == n) return {u, w};
+		if (w != v && 2 * s[w] > n) return dfs2(w, u, n);
+	}
+	return {u, -1};
+}
+
+pair<int, int> find_centroid(int root) {
+	// s muss nicht initialisiert werden, nur groß genug sein
+	dfs1(root);
+	return dfs2(root, -1, s[root]);
+}
-- 
cgit v1.2.3