From c97d2d14c071d19f9310839b6f9b2d2bdebf363b Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Tue, 28 Feb 2023 17:27:39 +0100
Subject: simplified tree isomorphism

---
 graph/treeIsomorphism.cpp | 56 +++++++++++++----------------------------------
 1 file changed, 15 insertions(+), 41 deletions(-)

(limited to 'graph/treeIsomorphism.cpp')

diff --git a/graph/treeIsomorphism.cpp b/graph/treeIsomorphism.cpp
index f3e147b..7a1be5b 100644
--- a/graph/treeIsomorphism.cpp
+++ b/graph/treeIsomorphism.cpp
@@ -1,41 +1,15 @@
-vector<vector<vector<int>>>
-getTreeLabel(const vector<vector<int>>& adj, int root) {
-	vector<vector<int>> level = {{root}};
-	vector<int> dist(sz(adj), -1);
-	dist[root] = 0;
-	queue<int> q;
-	q.push(root);
-	while (!q.empty()) {
-		int c = q.front();
-		q.pop();
-		for (int n : adj[c]) {
-			if (dist[n] < 0) {
-				dist[n] = dist[c] + 1;
-				if (sz(level) <= dist[n]) level.push_back({});
-				level[dist[n]].push_back(n);
-				q.push(n);
-	}}}
-	
-	vector<vector<vector<int>>> levelLabels(sz(level));
-	vector<int> shortLabel(sz(adj));
-	for (int l = sz(level) - 1; l >= 0; l--) {
-		vector<pair<vector<int>, int>> tmpLabels;
-		for (int v : level[l]) {
-			vector<int> label;
-			for (int n : adj[v]) {
-				if (dist[n] > dist[v]) {
-					label.push_back(shortLabel[n]);
-			}}
-			sort(all(label));
-			tmpLabels.push_back({label, v});
-		}
-		sort(all(tmpLabels));
-		vector<int>& last = tmpLabels[0].first;
-		int curId = 0;
-		for (auto& e : tmpLabels) {
-			levelLabels[l].push_back(e.first);
-			if (e.first != last) curId++, last = e.first;
-			shortLabel[e.second] = curId;
-	}}
-	return levelLabels;
-} 
+vector<vector<int>> adj;
+map<vector<int>, int> known;
+
+int treeLabel(int root, int p = -1) {
+	vector<int> children;
+	for (int x : adj[root]) {
+		if (x == p) continue;
+		children.push_back(treeLabel(x, root));
+	}
+	sort(all(children));
+	if (known.find(children) == known.end()) {
+		known[children] = sz(known);
+	}
+	return known[children];
+}
-- 
cgit v1.2.3