SGU101[Domino]

欧拉路。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-8-24

DESCRIPTION:

$DESCRIPTION

*/

#include <iostream>

using namespace std;

 

const int MAXE=100*2;

const int MAXV=60+1;

typedef struct struct_edge* edge;

struct struct_edge{int v,id;char dir;edge n;};

struct_edge pool[MAXE];

edge top=pool;

edge adj[MAXV];

int degree[MAXV];

int used[MAXE/2];

int list[MAXE/2+1];

int listtop;

int size[MAXV][MAXV];

edge edges[MAXV][MAXV][MAXE];

int printed[MAXE/2];

void add_edge(int u,int v,int id)

{

     degree[u]++,edges[u][v][size[u][v]++]=top,

     top->v=v,top->id=id,top->dir=’+’,top->n=adj[u],adj[u]=top++;

     degree[v]++,edges[v][u][size[v][u]++]=top,

     top->v=u,top->id=id,top->dir=’-‘,top->n=adj[v],adj[v]=top++;

}

void find_circuit(int u)

{

     for (edge i=adj[u];i;i=i->n)

         if (!used[i->id])

         {

            used[i->id]=true;

            find_circuit(i->v);

         }

     list[listtop++]=u;

}

void print(int u,int v)

{

     for (int i=0;i<size[u][v];i++)

         if (!printed[edges[u][v][i]->id])

         {

            cout<<edges[u][v][i]->id+1<<” “<<edges[u][v][i]->dir<<endl;

            printed[edges[u][v][i]->id]=true;

            break;

         }

}

 

int main()

{

    int N,a,b;

    cin>>N;

    for (int i=0;i<N;i++)

        cin>>a>>b,add_edge(a,b,i);

    int odc=0;

    int S;

    for (int u=0;u<MAXV;u++)

        if (degree[u])

           S=u;

    #define odd(x) ((x)&1)

    for (int u=0;u<MAXV;u++)

        if (odd(degree[u]))

           odc++,S=u;

    if (odc==0||odc==2)

    {

       find_circuit(S);

       if (listtop==N+1)

          for (int i=1;i<listtop;i++)

              print(list[i-1],list[i]);

       else cout<<“No solution”<<endl;

    }

    else cout<<“No solution”<<endl;

}