(UVA) 775 - Hamiltonian Cycle [Hamiltonian Cycle]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=716

Hamitioniam Cycle，就是經過每個點，最後形成環！

http://www.csie.ntnu.edu.tw/~u91029/Circuit.html#1

可以參考這個喔！

反正我是記得：圓環變成路徑，路徑變成圓環！如果沒有的話，就往外擴張。

理論上是O (V^2)了，可是我不小心code成 O(V^2 lg V) set 的部分！

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <set>
using namespace std;

const int MAX_N = 261;
int w[MAX_N][MAX_N];
int f[MAX_N],b[MAX_N]; //front, back

int main (){
//    ios::sync_with_stdio(0);
//    cin.tie(0);
    int n;
    while (cin >> n) {
//        cout<<"in\n";
        getchar();
        string ss;
        memset(w,0,sizeof(w));
        while (1) {
            getline(cin,ss);
            if (ss=="%") break;
//            cout<<"s="<<s<<".\n";
            int i=0,j=0;
            int len=ss.size();
            bool check=false;
            for (int x=0;len>x;x++) {
                if (check && '0'<=ss[x] && ss[x]<='9') {
                    j*=10;
                    j += (ss[x]-'0');
                }
                else if (!check && '0'<=ss[x] && ss[x]<='9') {
                    i*=10;
                    i += (ss[x]-'0');
                }
                else if (ss[x] == ' ') check=true;
            }
//            cout<<"i="<<i<<" , j="<<j<<" test\n";
            w[i][j] = 1;
            w[j][i] = 1;
        }
        memset(b,0,sizeof(b));
        memset(f,0,sizeof(f));
        int p1=1,pn=1;
        int cnt=1;
        int edg=0;
        bool cycle=false;
        bool ans=false;
        set<int> s;
        s.insert(1);
        while (1) {
//            if (cnt==1) goto aaa;
//            cout<< " queue : ";
//            printf("%d ",p1);
//            for (int x=f[p1];;x=f[x]) {
//                if (x==0) break;
//                if (x==p1) {
//                    printf("%d\n",x);
//                    break;
//                }
//                else printf("%d ",x);
//            }
//            aaa:
//            cout<<"p1="<<p1<<" , pn="<<pn<<" , cnt="<<cnt<<endl;
//            cout<<"cnt = "<<cnt<<endl;
            if (cycle) {
                if (cnt == n) {
                    ans=true;
                    break;
                }
                //get a something else
                bool GET=false;
                for (int i=1;n>=i;i++) {
                    if (s.find(i) == s.end()) {  //not in cycle
                        for (int j=1;n>=j;j++) {
                            if (i!=j && w[i][j]==1 && s.find(j) != s.end()) {
                                int tmp=f[j];
                                f[j] = i;
                                b[i] = j;
                                b[tmp]=0;
                                s.insert(i);
                                p1=tmp;
                                pn=i;
                                cnt++;
                                GET=true;
                                break;
                            }
                        }
                    }
                    if (GET) break;
                }
                cycle=false;
            }
//            cout<<"in\n";
            //become cycle
            bool move = false;
            for (int x=p1;x != pn; x=f[x]) {
                int nxt=f[x];
                if (w[nxt][p1] == 1 && w[x][pn] == 1) {
                    move=true;
                    f[x] = pn;
                    for (int i=pn;i!=nxt;i=f[i]) {
                        f[i] = b[i];
                        b[i] = x;
                        x=i;
                    }
                    f[nxt]=p1;
                    b[p1]=nxt;
                    b[nxt]=x;
                    break;
                }
            }
//            cout<<"in\n";
            cycle=move;
            if (!move) {
                for (int i=1;n>=i;i++) {
                    if (pn != i && s.find(i) == s.end() && w[i][pn] == 1) {
                        f[pn] = i;
                        b[i] = pn;
                        pn=i;
                        s.insert(i);
                        cnt++;
                        cycle=false;
                        break;
                    }
                }
                for (int i=1;n>=i;i++) {
                    if (p1 != i && s.find(i) == s.end() && w[i][p1] == 1) {
                        f[i] = p1;
                        b[p1] = i;
                        p1=i;
                        s.insert(i);
                        cnt++;
                        cycle=false;
                        break;
                    }
                }
            }
//            system("pause");
        }
        if (cnt==n) {
            printf("%d ",p1);
            for (int x=f[p1];;x=f[x]) {
                if (x==p1) {
                    printf("%d\n",x);
                    break;
                }
                else printf("%d ",x);
            }
        }
        else puts("N");
        
    }
}