题意 : 给出 N 个点（最多 1e6 ）和 M 条边 （最多 N + 20 条 ）要你输出一条从 1 开始回到 1 的哈密顿回路路径，不存在则输出 " There is no route, Karl! "
分析 :
题意很简单明了
众所周知，哈密顿回路是个 NP-Hard 问题
这么多个点的哈密顿回路肯定是不能暴力去寻找的
但是关注到 M ≤ N + 20 这个特殊的条件
那就说明图中肯定有很多单向链
那么这题就很明确了，就把所有的单链缩成一个点
然后再去 DFS 暴力找
口胡起来貌似很简单，写起来是真的 _(´ཀ`」 ∠)_
写了我挺久的，主要是Debug了挺久
#include<bits/stdc++.h>
using namespace std;
;
];
];///记录链的出度和入度
int N, M, Head[maxn], cnt;
int id, st;///分配ID的计数变量、寻找哈密顿回路的起点
int IN[maxn], OUT[maxn];///每个点的入度和出度数量，方便判断一个节点是否为单链的节点
int ID[maxn], vtx[maxn];///每个节点重新分配的ID、每个ID对应的节点or链
bool isChain[maxn], vis[maxn];///判断是否是链、DFS中的判重数组
int c[maxn];///并查集数组，判断图是否弱连通
vector<int> arr;///存储最终答案
int Findset(int x)
{
int root = x;
while(c[root] != root)
root = c[root];
int idx;
while(c[x] != root){
idx = c[x];
c[x] = root;
x = idx;
}
return root;
}
inline void Join(int a, int b)
{
int A = Findset(a);
int B = Findset(b);
if(A != B) c[A] = B;
}
inline void init()
{
; i<maxn; i++) c[i] = i;
memset(ID, -, sizeof(ID));
memset(vtx, -, sizeof(vtx));
memset(Head, -, sizeof(Head));
memset(isChain, false, sizeof(isChain));
cnt = id = ;
st = -;
}
inline void AddEdge(int From, int To)
{
Edge[cnt].v = To;
Edge[cnt].nxt = Head[From];
Head[From] = cnt++;
}
inline void ColorChain(int v, int Eiv, int Eid)
{
Chain[id][] = v;
bool loop = false;///链有可能构成环、如果是环，则出入度是一样的，标记一下
|| OUT[Eiv] != )){
) { ID[Eiv] = id; ) vtx[id] = Eiv; }
else { loop = true; break; }
isChain[Eiv] = true;
Eiv = Edge[Eid].v;
Eid = Head[Eiv];
}
Chain[id][] = loop ? v : Eiv;
id++;
}
inline void Color(int v)
{
&& OUT[v] == ) return;///如果是单链上的节点就跳过，因为我的染色找链
///总是去找链的入度节点才去为这个链分配ID
Chain[id][] = v, Chain[id][] = -;///可以无视这个，没啥用
ID[v] = id++;
vtx[id-] = v;
int Eid, Eiv;
; i=Edge[i].nxt){
Eiv = Edge[i].v;
Eid = i;
&& OUT[Eiv] == )///说明v是一个链的入度
ColorChain(v, Eiv, Head[Eiv]);///为链染色
}
}
int ans[maxn];
bool DFS(int v, int num)///寻找哈密顿回路，分是否是链的两种情况
{
if(num == id && v == st) return true;
if(vis[ID[v]]) return false;
vis[ID[v]] = true;
ans[num] = ID[v];
if(isChain[v]){
], num+) )///如果是链的开头，直接递归进其出度
return true;
}else{
; i=Edge[i].nxt)///如果不是链则正常访问其所有出度
) )
return true;;
}
vis[ID[v]] = false;
return false;
}
inline void Print_Chain(int v, int Chain_id)
{
&& OUT[v]==){
arr.push_back(v);
v = Edge[Head[v]].v;
}
}
int main(void)
{
freopen("king.in", "r", stdin);///提交记得加这两个 freopen
freopen("king.out", "w", stdout);
scanf("%d %d", &N, &M);
init();
int From, To;
while(M--){
scanf("%d %d", &From, &To);
AddEdge(From, To);
Join(From, To);
IN[To]++, OUT[From]++;
}
);
; i<=N; i++){
if(Findset(i) != root){
puts("There is no route, Karl!");
;
}
}
; i<=N; i++){
&& (IN[i] != || OUT[i] != )) st = i;
) continue;
else Color(i);///给每一个点配上一个ID，如果是链，则链上顶点ID一致，
///且当前节点 isChain = true 标记是链
}
){
;
bool flag = true;
){
flag = false;
printf("%d ", v);
v = Edge[Head[v]].v;
}puts(");
;
}
memset(vis, false, sizeof(vis));
)){
; i<id; i++){
int cur = vtx[ans[i]];
if(isChain[cur]) Print_Chain(cur, ans[i]);
else arr.push_back(cur);
}
bool BEGIN = false;
;
int len = arr.size();
; i<len && Count<len; i=(i+)%len){///因为不保证总是从1开始dfs，所以要去调整一下输出
) BEGIN = true;
if(BEGIN){
printf("%d ", arr[i]);
Count++;
}
}puts(");
}else puts("There is no route, Karl!");
;
}
/*
10 11
10 8
5 4
9 1
4 3
7 2
2 6
6 5
8 9
1 7
10 3
3 10
*/