本文共 1289 字，大约阅读时间需要 4 分钟。

题意：给你一些珠子，让你串成一个链，其中要求相邻的珠子相邻部分颜色相同。珠子的颜色用数字表示，范围从1到50.

思路：如果能串成一条链，那么说明从任意点出发都可以回到原处，其实就是判断欧拉回路。我们首先判断所有珠子的度数是不是偶数，如果不是偶数肯定不可以，由判断欧拉回路的条件可知，如果所有珠子的度数都是偶数，那么一定存在一条欧拉回路。我们只需要输出欧拉回路即可。

在输出欧拉回路的时候我们用dfs输出，注意是逆序输出，这个地方可能有点抽象，自己出一组数据理解一些，例如（1->2->3->2->1），逆序输出主要是防止回溯的时候出现连不成串的情况出现。

#include 
   
    #define N 55#define MAX 1010int g[N][N],vis[N];int d[N];int n;int cnt;void euler(int u){    int v;    for(v=1; v<=50; v++)        if(g[u][v])        {            g[u][v]--;            g[v][u]--;            euler(v);            printf("%d %d\n",v,u);        }}int main(){    int t,T;    int i,j;    int u,v;    scanf("%d",&T);    for(t=1 ; t<=T; t++)    {        cnt=0;        memset(g,0,sizeof(g));        memset(vis,0,sizeof(vis));        memset(d,0,sizeof(d));        scanf("%d",&n);        for(i=1 ; i<=n; i++)        {            scanf("%d%d",&u,&v);            d[u]++;            d[v]++;            g[u][v]++;            g[v][u]++;        }        printf("Case #%d\n",t);        //图是连通的，要判断所有点的度是否有为偶数        for(i=1 ; i<=50; i++)            if( d[i]%2 )                break;        if(i<=50)            printf("some beads may be lost\n");        else  //图连通而且所有点的度都为偶数，则是一个欧拉回路，输出路径            for(i=1; i<=50; i++)                euler(i);        if(t!=T) printf("\n");    }    return 0;}
   

转载地址：http://bbgsi.baihongyu.com/