# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1207426 | Trn115 | 지도 색칠하기 (GA3_map) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
static int N, M;
static int *A, *B;
inline int getbit(int x, int i) {
return (x >> (i - 1)) & 1;
}
inline void invertbit(int &x, int i) {
x ^= (1 << (i - 1));
}
long long NumberOfMaps (int N, int M, int *A, int *B) {
vector<vector<int>> g(N + 1);
for (int i = 0; i < M; ++i) {
g[A[i]].push_back(B[i]);
g[B[i]].push_back(A[i]);
}
int si = 1LL << N;
int res = 0, mask;
vector<int> color;
bool sat[2];
function<void(int, int, int)> dfs = [&](int v, int c, int type) {
color[v] = c;
for (int u : g[v]) {
if (getbit(mask, u) != type) continue;
if (color[u] == -1) {
dfs(u, c ^ 1, type);
} else if (color[u] == c) {
sat[type] = false;
}
}
};
for (mask = 0; mask < si; ++mask) {
color.assign(N + 1, -1);
int cc = 0;
sat[0] = sat[1] = true;
for (int i = 1; i <= N; ++i) {
if (getbit(mask, i) == 0 && color[i] == -1) {
dfs(i, 0, 0);
++cc;
}
}
for (int i = 1; i <= N; ++i) {
if (getbit(mask, i) == 1 && color[i] == -1) {
dfs(i, 0, 1);
++cc;
}
}
if (sat[0] && sat[1]) res += 1LL << cc;
}
return res;
}