Add centroid decomp

1 files changed, 22 insertions, 0 deletions

diff --git a/Graph/centroid.cpp b/Graph/centroid.cpp
new file mode 100644
index 0000000..3676d25
--- /dev/null
+++ b/Graph/centroid.cpp
@@ -0,0 +1,22 @@
+namespace centroid {
+    int sz[MN], cpar[MN], vis[MN];
+	void dfs(vector<int> * G, int u, int p = 0) {
+		sz[u] = 1;
+		for (int v : G[u]) if (v != p && !vis[v]) dfs(G, v, u), sz[u] += sz[v];
+	}
+	int centroid(vector<int> * G, int u) {
+		dfs(G, u);
+		int num = sz[u], p = 0;
+		do {
+			int nxt = 0;
+			for (int v : G[u]) if (v != p && !vis[v] && 2*sz[v] > num) nxt = v;
+			p = u, u = nxt;
+		} while (u);
+		return p;
+	}
+	void centroid_decomp(vector<int> * G, int u = 1, int p = 0) {
+		int c = centroid(G, u);
+		vis[c] = 1,	cpar[c] = p;
+		for (int v : G[c]) if (!vis[v]) centroid_decomp(G, v, c);
+	}
+}