In this HackerEarth Isomorphic Trees problem solution You are given two trees. You are allowed to perform an operation several times: attaching a new vertex connect to an existing vertex of a tree. For each vertex A of the first tree and vertex B of second tree, we root the first tree at A and the second tree at B then your task is to find the minimum number of operations needed to make two trees isomorphic.
(Two rooted trees are isomorphic if they are the same size N, and there is a permutation P of {1,2,...,N} such that P["root of the first tree"] = "root of the second tree" and there is an edge between u,v in the first tree iff there is an edge between P[u],P[v] in the second tree.)
HackerEarth Isomorphic Trees problem solution.
#include <bits/stdc++.h>
using namespace std;
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int FFTMOD = 1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";
template<class T, T oo> struct Hungary {
static const int MAXN = 1000 + 5;
static const int MAXM = 1000 + 5;
int nx, ny, maty[MAXM], frm[MAXM], used[MAXM];
T cst[MAXN][MAXM], fx[MAXN], fy[MAXM], dst[MAXM];
void init(int nx, int ny) {
this->nx = nx, this->ny = ny;
fill_n(fx, nx + 1, 0), fill_n(fy, ny + 1, 0);
fill_n(maty, nx + 1, 0);
for (int i = 0; i <= nx; i++) {
fill_n(cst[i], ny + 1, oo);
}
}
void add(int x, int y, int c) {
cst[x][y] = c;
}
T mincost() {
for (int x = 1; x <= nx; x++) {
int y0 = 0;
maty[0] = x;
for (int y = 0; y <= ny; y++) {
dst[y] = oo + 1;
used[y] = 0;
}
do {
used[y0] = 1;
int x0 = maty[y0], y1;
T delta = oo + 1;
for (int y = 1; y <= ny; y++) if (!used[y]) {
T curdst = cst[x0][y] - fx[x0] - fy[y];
if (dst[y] > curdst) {
dst[y] = curdst;
frm[y] = y0;
}
if (delta > dst[y]) {
delta = dst[y];
y1 = y;
}
}
for (int y = 0; y <= ny; y++) if (used[y]) {
fx[maty[y]] += delta;
fy[y] -= delta;
}
else {
dst[y] -= delta;
}
y0 = y1;
}
while (maty[y0] != 0);
do {
int y1 = frm[y0];
maty[y0] = maty[y1];
y0 = y1;
}
while (y0);
}
T res = 0;
for (int y = 1; y <= ny; y++) {
int x = maty[y];
if (cst[x][y] < oo) res += cst[x][y];
}
return res;
}
};
Hungary<int, (int) 1e9> hungary;
const int maxn = 50 + 5;
int dj[maxn];
int n, m;
vi adj1[maxn];
vi adj2[maxn];
int dp[maxn][maxn][maxn][maxn];
int size1[maxn][maxn];
int size2[maxn][maxn];
int find(int u) {
return dj[u] == u ? dj[u] : dj[u] = find(dj[u]);
}
int join(int u, int v) {
int p = find(u);
int q = find(v);
if (p != q) {
dj[p] = q;
return 1;
}
return 0;
}
void dfs1(int u, int p) {
size1[u][p] = 1;
for (int v : adj1[u]) {
if (v != p) {
dfs1(v, u);
size1[u][p] += size1[v][u];
}
}
}
void dfs2(int u, int p) {
size2[u][p] = 1;
for (int v : adj2[u]) {
if (v != p) {
dfs2(v, u);
size2[u][p] += size2[v][u];
}
}
}
int calc(int u, int pu, int v, int pv) {
int& res = dp[u][pu][v][pv];
if (~res) return res;
res = INF;
vi v1, v2;
for (int nu : adj1[u]) {
if (nu != pu) {
v1.pb(nu);
}
}
for (int nv : adj2[v]) {
if (nv != pv) {
v2.pb(nv);
}
}
vector<vi> cost(sz(v1), vi(sz(v2)));
FOR(i, 0, sz(v1)) FOR(j, 0, sz(v2)) {
cost[i][j] = calc(v1[i], u, v2[j], v);
}
int k = max(sz(v1), sz(v2));
hungary.init(k, k);
FOR(i, 0, sz(v1)) FOR(j, 0, sz(v2)) {
hungary.add(i + 1, j + 1, cost[i][j]);
}
FOR(i, 0, sz(v1)) {
FOR(j, sz(v2), k) {
hungary.add(i + 1, j + 1, size1[v1[i]][u]);
}
}
FOR(j, 0, sz(v2)) {
FOR(i, sz(v1), k) {
hungary.add(i + 1, j + 1, size2[v2[j]][v]);
}
}
FOR(i, sz(v1), k) FOR(j, sz(v2), k) {
hungary.add(i + 1, j + 1, 0);
}
return res = hungary.mincost();
}
void chemthan() {
cin >> n >> m;
assert(1 <= n && n <= 50);
assert(1 <= m && m <= 50);
FOR(i, 0, n) dj[i] = i;
FOR(i, 0, n - 1) {
int u, v; cin >> u >> v; u--, v--;
assert(0 <= u && u < n);
assert(0 <= v && v < n);
assert(join(u, v));
adj1[u].pb(v), adj1[v].pb(u);
}
FOR(u, 0, n) FOR(v, 0, n) dfs1(u, v);
FOR(i, 0, m) dj[i] = i;
FOR(i, 0, m - 1) {
int u, v; cin >> u >> v; u--, v--;
assert(0 <= u && u < m);
assert(0 <= v && v < m);
assert(join(u, v));
adj2[u].pb(v), adj2[v].pb(u);
}
FOR(u, 0, m) FOR(v, 0, m) dfs2(u, v);
ms(dp, -1);
FOR(u, 0, n) FOR(v, 0, m) cout << calc(u, u, v, v) << " \n"[v == m - 1];
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0), cin.tie(0);
if (argc > 1) {
assert(freopen(argv[1], "r", stdin));
}
if (argc > 2) {
assert(freopen(argv[2], "wb", stdout));
}
chemthan();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
} Second solution
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Stream;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
IsomorphicTrees solver = new IsomorphicTrees();
solver.solve(1, in, out);
out.close();
}
static class IsomorphicTrees {
int[] n;
List<Integer>[][] g;
public int[][][][] dp;
public int[][][] sz;
public void solve(int testNumber, InputReader in, OutputWriter out) {
n = new int[2];
n[0] = in.nextInt();
n[1] = in.nextInt();
g = new List[2][];
g[0] = LUtils.genArrayList(n[0] + 1);
g[1] = LUtils.genArrayList(n[1] + 1);
for (int k = 0; k < 2; k++) {
for (int i = 0; i < n[k] - 1; i++) {
int a = in.nextInt(), b = in.nextInt();
g[k][a].add(b);
g[k][b].add(a);
}
}
dp = new int[n[0] + 1][n[0] + 1][n[1] + 1][n[1] + 1];
sz = new int[2][][];
sz[0] = new int[n[0] + 1][n[0] + 1];
sz[1] = new int[n[1] + 1][n[1] + 1];
AUtils.deepFill(dp, -1);
AUtils.deepFill(sz, -1);
for (int i = 1; i <= n[0]; i++) {
for (int j = 1; j <= n[1]; j++) {
if (j != 1) out.print(" ");
out.print(solve(0, i, 0, j));
}
out.println();
}
}
public int getSize(int k, int p, int c) {
if (sz[k][p][c] != -1) return sz[k][p][c];
int r = 1;
for (int n : g[k][c]) {
if (p == n) continue;
r += getSize(k, c, n);
}
return sz[k][p][c] = r;
}
public int solve(int p1, int c1, int p2, int c2) {
if (dp[p1][c1][p2][c2] != -1) return dp[p1][c1][p2][c2];
int s1 = g[0][c1].size() - (p1 == 0 ? 0 : 1);
int s2 = g[1][c2].size() - (p2 == 0 ? 0 : 1);
int n = Math.max(s1, s2);
int[][] mat = new int[n + 1][n + 1];
int id1 = 1;
for (int n1 : g[0][c1]) {
if (n1 == p1) continue;
int id2 = 1;
for (int n2 : g[1][c2]) {
if (n2 == p2) continue;
mat[id1][id2] = solve(c1, n1, c2, n2);
id2++;
}
id1++;
}
id1 = 1;
for (int n1 : g[0][c1]) {
if (n1 == p1) continue;
int t = getSize(0, c1, n1);
for (int j = s2 + 1; j <= s1; j++) mat[id1][j] = t;
id1++;
}
int id2 = 1;
for (int n2 : g[1][c2]) {
if (n2 == p2) continue;
int t = getSize(1, c2, n2);
for (int j = s1 + 1; j <= s2; j++) mat[j][id2] = t;
id2++;
}
return dp[p1][c1][p2][c2] = Hungarian.minWeightPerfectMatching(mat);
}
}
static class AUtils {
public static void deepFill(int[][][][] x, int val) {
for (int[][][] y : x) deepFill(y, val);
}
public static void deepFill(int[][][] x, int val) {
for (int[][] y : x) deepFill(y, val);
}
public static void deepFill(int[][] x, int val) {
for (int[] y : x) deepFill(y, val);
}
public static void deepFill(int[] x, int val) {
Arrays.fill(x, val);
}
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1 << 16];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (this.numChars == -1) {
throw new InputMismatchException();
} else {
if (this.curChar >= this.numChars) {
this.curChar = 0;
try {
this.numChars = this.stream.read(this.buf);
} catch (IOException var2) {
throw new InputMismatchException();
}
if (this.numChars <= 0) {
return -1;
}
}
return this.buf[this.curChar++];
}
}
public int nextInt() {
int c;
for (c = this.read(); isSpaceChar(c); c = this.read()) {
;
}
byte sgn = 1;
if (c == 45) {
sgn = -1;
c = this.read();
}
int res = 0;
while (c >= 48 && c <= 57) {
res *= 10;
res += c - 48;
c = this.read();
if (isSpaceChar(c)) {
return res * sgn;
}
}
throw new InputMismatchException();
}
public static boolean isSpaceChar(int c) {
return c == 32 || c == 10 || c == 13 || c == 9 || c == -1;
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println() {
writer.println();
}
public void close() {
writer.close();
}
public void print(int i) {
writer.print(i);
}
}
static class LUtils {
public static <E> List<E>[] genArrayList(int size) {
return Stream.generate(ArrayList::new).limit(size).toArray(List[]::new);
}
}
static class Hungarian {
public static int minWeightPerfectMatching(int[][] a) {
int n = a.length - 1;
int m = a[0].length - 1;
int[] u = new int[n + 1];
int[] v = new int[m + 1];
int[] p = new int[m + 1];
int[] way = new int[m + 1];
for (int i = 1; i <= n; ++i) {
int[] minv = new int[m + 1];
Arrays.fill(minv, Integer.MAX_VALUE);
boolean[] used = new boolean[m + 1];
p[0] = i;
int j0 = 0;
while (p[j0] != 0) {
used[j0] = true;
int i0 = p[j0];
int delta = Integer.MAX_VALUE;
int j1 = 0;
for (int j = 1; j <= m; ++j)
if (!used[j]) {
int d = a[i0][j] - u[i0] - v[j];
if (minv[j] > d) {
minv[j] = d;
way[j] = j0;
}
if (delta > minv[j]) {
delta = minv[j];
j1 = j;
}
}
for (int j = 0; j <= m; ++j)
if (used[j]) {
u[p[j]] += delta;
v[j] -= delta;
} else
minv[j] -= delta;
j0 = j1;
}
while (j0 != 0) {
int j1 = way[j0];
p[j0] = p[j1];
j0 = j1;
}
}
int[] matching = new int[n + 1];
for (int i = 1; i <= m; ++i)
matching[p[i]] = i;
return -v[0];
}
}
}
0 Comments