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"); } }
