Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth Isomorphic Trees problem solution

YASH PAL, 31 July 2024
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

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 << "msn";
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];
}

}
}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes