content/graph/treeIsomorphism.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector<vector<int>> adj;
map<vector<int>, int> known; // dont reset!

int treeLabel(int v, int from = -1) {
	vector<int> children;
	for (int u : adj[v]) {
		if (u == from) continue;
		children.push_back(treeLabel(u, v));
	}
	sort(all(children));
	if (known.find(children) == known.end()) {
		known[children] = sz(known);
	}
	return known[children];
}