@[卢安来](/space/show?uid=38502) 考场代码勿喷
1.用邻接矩阵存图最快了,可以卡着空间过
2.std::sort应该比手打的要快
3.再加个最优性剪枝(比当前最小的大就退出)速度就飞起了
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define RI register int
using namespace std;
const int N = 5003;
int n, m, cnt, ct, num[N][N], su[N], st[N], nnn[N][N], in[N], bas[N], p, flag;
inline int dfs(int x, int fa) {
bas[++ct] = x;
if (x > st[ct] && !flag) return 0;
if (x < st[ct]) flag = 1;
for (RI i = 0; i < su[x]; ++i) if (!nnn[x][i] && !in[num[x][i]]) {
in[num[x][i]] = 1;
p = dfs(num[x][i], x); if (!p) return 0;
}
return 1;
}
inline int read() {
int x = 0, c;
while (!isdigit(c = getchar()));
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x;
}
int main() {
n = read(), m = read();
for (RI i = 1, u, v; i <= m; ++i) u = read(), v = read(), num[u][su[u]++] = v, num[v][su[v]++] = u;
for (RI i = 1; i <= n; ++i) sort(num[i], num[i] + su[i]), st[i] = n;
if (m == n - 1) {
in[1] = 1, dfs(1, 0);
for (RI i = 1; i <= n; ++i) st[i] = bas[i];
}
else {
for (RI i = 1; i <= n; ++i)
for (RI j = 0; j < su[i]; ++j) {
if (num[i][j] > i) {
nnn[i][j] = 1, in[1] = 1, dfs(1, 0);
if (ct == n) for (RI i = 1; i <= n; ++i) st[i] = bas[i];
nnn[i][j] = ct = flag = 0, memset(in, 0, sizeof in);
}
}
}
for (RI i = 1; i <= n; ++i) printf("%d ", st[i]);
return 0;
}
```
by touristX @ 2019-01-20 17:24:18