Challenge NPC 2

题目大意

给定$n(1 \le n \le 5 \cdot 10^5)$个点$m(0 \le m \le n - 1)$条边的无环森林，求它补图上的哈密尔顿路径，如果没有，输出$-1$。

解题思路

考虑对每棵树进行遍历，发现当树的深度大于$3$时，可以一步走完；当树的深度小于等于$3$的时候，可以分两步走完。当且仅当只有一棵树，且这棵树的深度小于等于$3$时没有哈密尔顿路径，因为无法将其分成两部分。

所以，对于每一棵树，首先求出它的一条直径，并存储这棵树上各个点的深度，若深度大于$3$，则先将偶数深度的点存入数组，再将奇数深度的点存入数组；若深度小于等于$3$，则分别存入对应的$vector$，最后加入答案的时候保证中间有其他的点即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define maxn 500100
#define int long long
using namespace std;
const double eps = 1e-8;
vector<int>e[maxn], res, tmp, t1, t2;
int dep[maxn], ind[maxn], c;
bool vis[maxn];

void dfs(int x, int fa, bool flag){
    if(flag)  vis[x] = true, tmp.push_back(x);
    for (auto u : e[x]) {
        if(u == fa)  continue;
        dep[u] = dep[x] + 1;
        if(dep[u] > dep[c])  c = u;
        dfs(u, x, flag);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);  e[v].push_back(u);
        ind[u]++, ind[v]++;
    }
    bool flag = false;
    for (int i = 1; i <= n; ++i)  if(ind[i] == n - 1)  flag = true;
    for (int i = 1; i <= n && !flag; ++i) {
        if(vis[i])  continue;
        tmp.clear();  c = i;
        dfs(i, 0, false);
        dep[c] = 1;
        dfs(c, 0, true);
        if(dep[c] == 1)  res.push_back(c);
        else if(dep[c] == 3 || dep[c] == 2) {
            for (auto u : tmp)  if(dep[u] & 1)  t1.push_back(u);
            for (auto u : tmp)  if(dep[u] % 2 == 0)  t2.push_back(u);
        }
        else {
            for (auto u : tmp)  if(dep[u] % 2 == 0)  res.push_back(u);
            for (auto u : tmp)  if(dep[u] & 1)  res.push_back(u);
        }
    }
    if(flag)  cout << -1;
    else {
        for (auto u : t1)  cout << u << ' ';
        for (auto u : res)  cout << u << ' ';
        for (auto u : t2)  cout << u << ' ';
    }
    cout << '\n';
    for (int i = 1; i <= n; ++i)  e[i].clear(), vis[i] = false, dep[i] = 0, res.clear(), t1.clear(), t2.clear(), ind[i] = 0;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  cout.tie(0);
    int t = 1;  cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}