Contest Duration: - (local time) (100 minutes) Back to Home

## C - Graph Isomorphism Editorial by en_translator

Let us define integers $$X_{i, j}$$ to be $$1$$ if there is a string connecting Balls $$i$$ and $$j$$ in Takahashi’s toy, and to be $$0$$ otherwise.
Similarly, let us define integers $$Y_{i, j}$$ to be $$1$$ if there is a string connecting Balls $$i$$ and $$j$$ in Aoki’s toy, and to be $$0$$ otherwise.

Consider brute forcing all the permutations $$P$$ of $$(1, 2, \dots, N)$$. Then $$P$$ satisfies the conditions if and only if:

• for all $$1 \leq i \leq N, 1 \leq j \leq N$$ it holds that $$X_{i, j} = Y_{P_i, P_j}$$.

One can check if this condition is satisfied in $$O(N^2)$$ time. Since there are $$N!$$ possible $$P$$’s, the overall time complexity is $$O(N^2 \times N!)$$, which will meet the time limit.

In order to iterate through all the permutations, we can use std::next_permutations in C++ or itertools.permutations in Python.

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
int n, m;
cin >> n >> m;
vector x(n, vector<bool>(n)), y(n, vector<bool>(n));
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
a -= 1, b -= 1;
x[a][b] = x[b][a] = true;
}
for (int i = 0; i < m; ++i) {
int c, d;
cin >> c >> d;
c -= 1, d -= 1;
y[c][d] = y[d][c] = true;
}
vector<int> p(n);
iota(begin(p), end(p), 0);
int ans = 0;
do {
bool ok = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (x[i][j] != y[p[i]][p[j]]) {
ok = false;
}
}
}
if (ok) {
cout << "Yes\n";
return 0;
}
} while (next_permutation(begin(p), end(p)));
cout << "No\n";
}


Sample code (Python) :

import itertools

n, m = map(int, input().split())
a = [[False] * n for _ in range(n)]
b = [[False] * n for _ in range(n)]

for _ in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
a[u][v] = a[v][u] = True

for _ in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
b[u][v] = b[v][u] = True

ans = False
for p in itertools.permutations(range(n)):
ok = True
for i in range(n):
for j in range(n):
if a[i][j] != b[p[i]][p[j]]:
ok = False
if ok:
ans = True
print("Yes" if ans else "No")


posted:
last update: