hdu 2894 DFS 欧拉回路

• 这应该是《离散数学》教材中关于欧拉回路的一道例题，模型很经典。

不要拘泥于过去邻接矩阵存储形式的做法！

从效率角度上着想，能得到更佳的解决方案

struct Edge
{
    int to,next,ve;
    Edge(){}
    Edge(int v,int w,int x):to(v),next(w),ve(x){}
} edge[maxn];
int head[maxn],cnt;

void addedge(int u,int v)
{
    if (u==v) return;
    edge[cnt]=Edge(v,head[u],v);
    head[u]=cnt++;

    /*edge[head[0]]=Edge(u,head[v]);
    head[v]=head[0]++;*/
}

bool vis[maxn];
int n,N;
vector<int> vec;

void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;

    for(int i=0;i<N;i++)
    {
        //cout<<i<<':'<<(i<<1)%N<<' '<<((i<<1)|1)%N<<' '<<((N|i)>>1)<<' '<<(i>>1)<<endl;
        /*mp[i][(i<<1)%N]++;
        mp[i][((i<<1)|1)%N]++;
        mp[i][(N|i)>>1]++;
        mp[i][i>>1]++;
        mp[i][i]=0;*/
        addedge(i+1,(i<<1)%N+1);
        addedge(i+1,((i<<1)|1)%N+1);
        //addedge(i,(N|i)>>1);
        //addedge(i,i>>1);
    }
}

void dfs(int u)
{

    for(int i=head[u];i>-1;i=edge[i].next)
    {
        int v=edge[i].to;
        //cout<<u<<' '<<v<<endl;
        if (vis[edge[i].ve]) continue;
        vis[edge[i].ve]=1;
        vec.push_back(edge[i].ve);
        dfs(v);
    }
}

int main()
{
    while(~scanf("%d",&n))
    {
        N=1<<n;
        init();
        vec.clear();

        CLEAR(vis,maxn);
        dfs(1);
        cout<<N<<' ';
        //cout<<vec[0];
        for(int i=0;i<vec.size();i++) cout<<(vec[i]&1);//cout<<vec[i]<<' ';
        cout<<endl;
    }
    return 0;
}