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 性质的图中寻找一条哈密顿回路。

数据范围：$2 \le N \le 1000$。

算法分析

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

若简单图$G$满足 Ore 性质，且阶数大于$2$，则图$G$中一定存在哈密顿回路。

考虑先从点$1$开始构造一条链，接着对这条链进行扩展：

• 在链上找到一点$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;

int read(char s[]) {
  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() {
    scanf("%d", &n), read(s);
    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; }
      int p = head;
      for (; nxt[p]; p = nxt[p])
        if (mp[nxt[p]][head] && mp[p][tail]) {
          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;
}