首先我们可以确认 1的值一定是0
题目要求的是 有边的两个点所代表的值二进制有一位不同(即有边相连的两个值二进制所包含的1的个数相差为1)
所以我们通过他给你的图进行BFS 把原图分为一圈一圈的 并且先给每一个点赋一个初值
这样每一圈内的值二进制所包含的1的个数往外递增且同一圈内值二进制所包含的1的个数是相等的 目前我们就得到了题目的一个可行解
题目追加要求最小字典序 我们发现把这2^n个数二进制表示出来 则有n列 任意两列之间的交换是不会影响值二进制中1的个数且符合边关系的
即交换二进制中的任意两列不会影响答案的正确性
所以我们就可以通过排列这个二维数组的字典序来得到 答案的最小字典序
#include<bits/stdc++.h>
using namespace std; inline void splay(int &v)
{
v = ;
char c = ;
int p = ;
while (c < '' || c > '')
{
if (c == '-')
{
p = -;
}
c = getchar();
}
while (c >= '' && c <= '')
{
v = (v << ) + (v << ) + c - '';
c = getchar();
}
v *= p;
}
const int N = ;
int n, m, dp[N], q[N], fir[N], sz, to[], nxt[], vis[N], inque[N];
struct Q
{
bool s[N];
int id;
} f[];
void add(int x, int y)
{
nxt[++sz] = fir[x], fir[x] = sz, to[sz] = y;
}
bool cmp(Q a, Q b)
{
for (int i = ; i <= ( << n); i++)
{
if (a.s[i] != b.s[i])
{
return a.s[i] > b.s[i];
}
}
return true;
}
int main()
{
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int T;
cin >> T;
while (T--)
{
cin >> n >> m;
for (int i = ; i <= ( << n); i++)
{
inque[i] = vis[i] = fir[i] = dp[i] = ;
}
sz = ;
for (int i = , u, v; i <= m; i++)
{
splay(u), splay(v);
add(u, v), add(v, u);
}
for (int i = ; i <= ( << n); i++)
{
dp[i] = ;
}
int t = ;
vis[] = ;
int hd = , tl = ;
for (int u = fir[]; u; u = nxt[u])
{
dp[to[u]] = << (t++);
q[++tl] = to[u];
}
while (hd != tl)
{
int v = q[++hd];
vis[v] = ;
for (int u = fir[v]; u; u = nxt[u])
{
if (!vis[to[u]])
{
dp[to[u]] |= dp[v];
if (!inque[to[u]])
{
q[++tl] = to[u];
inque[to[u]] = ;
}
}
}
}
for (int i = ; i < n; i++)
{
f[i].id = i;
}
for (int i = ; i <= ( << n); i++)
{
for (int j = ; j < n; j++)
{
f[j].s[i] = dp[i] >> j & ;
}
}
sort(f, f + n, cmp);
for (int i = ; i <= ( << n); i++)
{
int ret = ;
for (int j = ; j < n; j++)
{
if (f[j].s[i])
{
ret |= ( << j);
}
}
printf("%d%c", ret, " \n"[i == ( << n)]);
}
}
}