The Book

题目描述

There is a group of $N$ people which are numbered $1$ through $N$, and everyone of them has not less than $\left[ {N + 1 \over 2} \right]$ friends. A man with number $1$ has the book, which others want to read. Write the program which finds a way of transferring the book so that it will visit every man only once, passing from the friend to the friend, and, at last, has come back to the owner. Note: if A is a friend of B then B is a friend of A.

算法分析

Ore性质：一张阶数等于$N$的图中任意两个不相邻的点的度数之和不小于$N$。

• 在链上找到一点$p$（设它的下一个点是$q$），满足链头和$q$连通、链尾和$p$连通，可以删去$p$、$q$之间的边，连接链头和$q$、链尾和$p$，构成一个环；
• 如果环上的点数小于$N$，找到一个和环上一点$p$连通且不在环上的点$q$，可以删去一条$p$的边，连接$p$和$q$，构成一条链，回到上一步。

代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

char c = getchar(); int len = 0;
while (~ c && c != '\n') s[len ++] = c, c = getchar();
s[len] = '\0'; return len;
}

struct Solver {
private:
static const int N = 1010;
int n, pre[N], nxt[N], near[N];
bool mp[N][N], vis[N];
char s[N << 3];
void input() {
for (int i = 1; i <= n; ++ i) {
int len = read(s), t = 0;
for (int j = 0; j <= len; ++ j)
if (isdigit(s[j])) (t *= 10) += s[j] - '0'; else mp[i][t] = true, t = 0;
}
}
void dfs(int t, int fa) {
vis[t] = true;
for (int i = 1; i <= n; ++ i)
if (mp[t][i] && ! vis[i]) { nxt[t] = i, pre[i] = t, dfs(i, t); return; }
}
int get_pre(int t) { if (! pre[t]) return t; else return get_pre(pre[t]); }
int get_nxt(int t) { if (! nxt[t]) return t; else return get_nxt(nxt[t]); }
void reverse(int p) {
nxt[p] = pre[p]; if (! pre[p]) return; reverse(pre[p]), pre[pre[p]] = p;
}
void process() {
int cnt = 0; dfs(1, 0);
for (int i = 1; i <= n; ++ i) cnt += pre[i] || nxt[i];
for (int i = 1; i <= n; ++ i) if (pre[i] || nxt[i])
for (int j = 1; j <= n; ++ j) if (mp[i][j] && ! pre[j] && ! nxt[j]) near[j] = i;
while (cnt <= n) {
int head = 0, tail = 0;
for (int i = 1; i <= n; ++ i) if (pre[i]) { head = get_pre(i); break; }
for (int i = 1; i <= n; ++ i) if (nxt[i]) { tail = get_nxt(i); break; }
for (; nxt[p]; p = nxt[p])
int tmp = nxt[p]; pre[tmp] = nxt[p] = 0, reverse(p);
nxt[head] = tmp, pre[tmp] = head, nxt[tail] = p, pre[p] = tail;
break;
}
if (cnt < n)
for (int i = 1; i <= n; ++ i) if (! pre[i] && ! nxt[i] && near[i]) {
nxt[i] = near[i], nxt[pre[near[i]]] = 0, pre[near[i]] = i;
for (int j = 1; j <= n; ++ j) if (mp[i][j] && ! pre[j] && ! nxt[j]) near[j] = i;
break;
}
++ cnt;
}
int p = 1; putchar('1');
do printf(" %d", p = nxt[p]); while (p != 1);
putchar('\n');
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot