//多米诺骨牌算法
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#define VNUM 6    //顶点个数，在本题中，顶点个数总为6，即点数的个数
#define MAXN 101    //每个测试数据中骨牌的数目N的最大值，1<=N<=100
struct EdgeNode    //边链表中的边节点
{
    int adjvex;    //边(弧)的另一个邻接点的序号
    int EdgeNo;    //边的序号(即读入时的顺序)
    int flag;    //标记：1－正向，-1－反向
    EdgeNode *nextedge;    //指向下一个表节点
};
EdgeNode* EdgeLink[VNUM+1];    //各顶点的边链表(第0个元素不用)
int visited[MAXN];    //边的访问标志，为1表示已经访问过,初始为0
//欧拉通路(回路)上各边的序号
int path[MAXN];    //path[i]=j(j>0)表示第i条边为第j条边,不旋转;-j表示要旋转
int pi;    //path数组的下标
int N;        //每个测试数据中骨牌的数目
void CreateLG( ) //采用邻接表存储表示,构造有向图G
{
    int i;    //循环变量
    EdgeNode *p1, *p2;    //两个临时边节点
    int v1, v2;    //边的两个顶点
    memset( visited, 0, sizeof(visited) );    //边未访问
    for( i=1; i<=6; i++ )  EdgeLink[i] = NULL;    //各顶点边链表初始为"空"
    int number = 1;    //边的序号
    for( i=1; i<=N; i++ )    //N条边
    {
        scanf( "%d%d", &v1, &v2 );
        p1 = new EdgeNode;  p2 = new EdgeNode;    // 假定有足够空间
       
        p1->adjvex = v2;  p1->EdgeNo = number;    //边的序号
        p1->flag = 1;    //正向
        p1->nextedge = EdgeLink[v1];  EdgeLink[v1] = p1; //插入到顶点v1的边链表
       
        p2->adjvex = v1;  p2->EdgeNo = number;
        p2->flag = -1;    //反向
        p2->nextedge = EdgeLink[v2];  EdgeLink[v2] = p2; //插入到顶点v2的边链表
        number++;
    }
}
void DFSL( int start )    //无向图的深度优先搜索算法，图用邻接表表示
{
    while( pi<=N )    //还有边没有访问到
    {
        EdgeNode *p;
        p = EdgeLink[start];
        while( p!=NULL )
        {
            if( !visited[p->EdgeNo] )    //第cstring转为intp->Edgeno条边未访问过
            {
                //同一条边正向,逆向2个节点对应EdgeNo相同,保证不会走同一条路
                visited[p->EdgeNo] = 1;
                if( p->flag>0 )  path[pi] = p->EdgeNo; //不旋转
                else  path[pi] = -(p->EdgeNo);//要旋转
                pi++;
                DFSL( p->adjvex );
            }
            else  p = p->nextedge;
        }
    }
}
void Domino( )
{
    int JDNum = 0;//奇度顶点个数
    int start1, start2;//搜索的起始顶点
    EdgeNode* p;
    int i, j;    //循环变量
    for( i=1; i<=6; i++ )
    {
        int DNum = 0;//顶点的度数
        p = EdgeLink[i];
        while( p!=NULL )    //统计顶点i的度数
        {
            DNum++;  p = p->nextedge;
        }
        if( DNum%2!=0 )
        {
            start1 = i; JDNum++;
        }
        if( DNum!=0 )  start2 = i;
    }
    if( JDNum!=0 && JDNum!=2 ) //不存在欧拉通路
    {
        printf( "No Solution!\n" );  return;
    }
   
    pi = 1;    //path数组的下标
    //存在欧拉通路（回路），还得选对起点
    if( JDNum==2 )  DFSL( start1 );    //欧拉通路,从start顶点开始搜索
    else  DFSL( start2 );    //欧拉回路,从顶点1开始搜索
   
    char flag1 = '+', flag2 = '-';
    for( i=1; i<=N; i++ )
    {
        if( path[i]>0 )    //输出欧拉通路上第i条的序号及旋转标志
            printf( "%d%c\n", path[i], flag1 );
        else  printf( "%d%c\n", -path[i], flag2 );
    }
}
void DeleteLG( ) //释放各顶点边链表中的边结点所占的存储空间
{
    int i;    //循环变量
    EdgeNode *pi;    //用来指向边链表中各边节点的指针
    for( i=1; i<=6; i++ )
    {
        pi = EdgeLink[i];
        while( pi!=NULL )    //释放第i个顶点边链表各边结点所占的存储空间
        {
            EdgeLink[i] = pi->nextedge;  delete pi;
            pi = EdgeLink[i];
        }
    }
}
void main( )
{
    while( scanf( "%d", &N ) && N!=0 )
    {
        CreateLG( );    //创建邻接表
        Domino( );        //求解
        DeleteLG( );    //释放各边链表中的边结点
    }
}
代码来自www.dxsls

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。