SGU 122 The book 满足ore性质的哈密尔顿回路求法

这题ac的不容易啊，知道怎么做但是还是出现了许多错误，导致无限re。。。

由题目的条件知道图满足ore性质，所以有O(n2)的算法，1000个点，不会超时~

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;

#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif

#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a)         for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a)        for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define SZ(a)           ((int)a.size())
#define PP(n,m,a)       puts("---");FF(i,n){FF(j,m)cout << a[i][j] << ' ';puts("");}
#define pb              push_back
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)

const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-10;
const double pi = acos(-1.0);
const int maxn = 1011;

bool b[maxn][maxn];
bool link[maxn][maxn];
bool vis[maxn];
int s,t;
int re;
deque<int>z[maxn];
int a[maxn];
vector<int>v;
bool quan;
int n;
char ss[52202];
string sc;


void find(int now)
{
    for(int to=1;to<=n;to++)
    {
        if(b[now][to] && !vis[to])
        {
            vis[to]=true;
            v.pb(to);
            link[now][to]=true;
            link[to][now]=true;
            z[now].pb(to);
            z[to].pb(now);
            re++;
            t = to;
            find(to);
            return ;
        }
    }
}


void make_ring()
{
    if(b[t][s]==true)
    {
        link[s][t] = link[t][s] = true;
        z[s].pb(t);
        z[t].pb(s);
        quan = true;
        return ;
    }
    MM(a,0);
    int now,to;
    a[1]=s;
    a[2]=z[s][0];
    now=z[s][0];
    int temp = 2;
    while(true)
    {
        FF(i,z[now].size())
        {
            to=z[now][i];
            if(to!=a[temp-1])
            {
                now = to;
                a[temp+1] = to;
                temp++;
                break;
            }
        }
        if(a[temp]==t)
        {
            break;
        }
    }

    for(int i=2;;i++)
    {
        if(b[s][a[i+1]] && b[a[i]][t] )
        {
            link[a[i]][a[i+1]] = false;
            link[a[i+1]][a[i]] = false;
            link[a[i+1]][s] = link[s][a[i+1]] = true;
            link[t][a[i]] = link[a[i]][t] = true;
            z[a[i]].clear();
            z[a[i+1]].clear();
            z[a[i]].pb(a[i-1]);
            z[a[i]].pb(t);
            z[a[i+1]].pb(s);
            z[a[i+1]].pb(a[i+2]);
            z[s].pb(a[i+1]);
            z[t].pb(a[i]);
            quan=true;
            return ;
        }
    }
}

void add()
{
    int now,to;
    int net;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            now = i;
            FF(j,v.size())
            {
                to = v[j];
                if(b[now][to])
                {
                    net = z[to][1];
                    z[to].pop_back();
                    if(to==z[net][0])
                    {
                        z[net].pop_front();
                    }
                    else if(to ==z[net][1])
                    {
                        z[net].pop_back();
                    }
                    link[to][net] = link[net][to] = false;
                    link[now][to] = link[to][now] = true;
                    s=now;
                    t=net;
                    z[to].pb(now);
                    z[now].clear();
                    z[now].pb(to);
                    re++;
                    vis[now]=true;
                    quan =false;
                    return ;
                }
            }
        }
    }
}

void start()
{
    MM(link,false);
    v.clear();
    quan = false;
    re=1;
    vis[1]=true;
    v.pb(1);
    s=t=1;
    while(re<n)
    {
        find(t);
        if(quan==false)
        {
            make_ring();

        }
        if(re>=n)
        {
            break;
        }
        else
        {
            if(quan==true)
            add();
        }
    }

    if(!quan)
    {
        make_ring();
    }
    MM(a,0);
    a[0]=1;
    a[1]=z[1][0];
    int now=a[1],to;
    int temp = 1;
    int step = 1;
    while(step<=n+1)
    {
        FF(i,z[now].size())
        {
            to = z[now][i];
            if(to!=a[temp-1])
            {
                a[temp+1] = to;
                now = to;
                temp++;
                break;
            }
        }
        step++;
    }
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"1"<<endl;
    return ;
}

int main()
{
    while(cin>>n)
    {

        FF(i,maxn)
        {
            z[i].clear();
        }
        MM(b,false);
        int now;
        cin.getline(ss,200);
        for(int kk=1;kk<=n;kk++)
        {
            cin.getline(ss,50200);
            sc = ss;
            sc += " ";
            now = 0;
            for(int i=0;i<sc.length();i++)
            {
                if(sc[i]==' ')
                {
                    if(now)
                    {
                        b[kk][now] = b[now][kk] = true;
                    }
                    now = 0;
                }
                else
                {
                    now*=10;
                    now+=sc[i]-'0';
                }
            }
        }
        if(n==2)
        {
            cout<<"1 2 1\n"<<endl;
            continue;
        }
        start();
    }
    return 0;
}