SGU 122 The book

論文出處：
http://www.sciencedirect.com/science/article/pii/S0898122197002253

哈密頓迴路本是NP問題，但題目有加條件

條件：deg(u) + deg(v) >= |V|

先亂連一個圈，沒有相鄰也沒關係

對於一個在圈上相鄰卻在圖上沒有相鄰的點對

一定可以找到兩個在圈上相鄰的點對，且...就如圖所示：

至於原因的話，其實就是因為那個限制，可以自己證證看，蠻好玩的，概念跟n+1隻鴿子放入n個籠子中，至少有一個籠子會有兩隻鳥，是一樣的道理。

所以像前面這樣不斷的連連連，最多連n次，每次尋找的時間複雜度O(n)，所以整體的複雜度便是O(n^2)

//By momo
#include<cstdio>
#include<algorithm>
#define N 1010
using namespace std;

char che;
bool tbl[N][N];
int L[N], R[N];

int main(){
    int n; scanf("%d", &n);

    for(int i = 0, to; i < n; i++){
        while(1){
            scanf("%d", &to); tbl[i][to-1] = 1;
            char j = getchar();
            if(j == '\n' || j == '\r' || j == EOF) break;
        }
    }

    for(int i = 0; i < n; i++) R[i] = (i+1)%n;
    for(int i = 0; i < n; i++) L[i] = (i-1+n)%n;

    bool upd = 1;
    while(upd){
        upd = 0;
        int x = 0;
        while(1){
            if(tbl[x][R[x]] == 0){
                upd = 1;
                int y = 0;
                while(1){

                    int u = x, v = R[x];
                    int p = y, q = R[y];
                   
                    if(v != p && u != p && u != q){

                        if(tbl[u][p] && tbl[v][q]){
                            R[u] = L[u]; L[u] = p;
                            R[v] = R[v]; L[v] = q;
                            L[p] = L[p]; R[p] = u;
                            L[q] = R[q]; R[q] = v;
                            for(int z = R[u]; z != q; z = R[z])
                                swap(R[z], L[z]);
                            break;
                        }
                    }

                    y = R[y];
                    if(y == 0) break;
                }
                break;
            }
            x = R[x];
            if(x == 0) break;
        }
    }

    int x = 0;
    while(1){
        printf("%d ", x+1), x = R[x];
        if(x == 0) break;
    }
    puts("1");
}