学步园

欧拉回路，先判断其连通性和每个节点的度数的奇偶性（本题中所有节点都应为偶数），如果是欧拉回路则DFS输出结果，注意：每个“珍珠”的两个数字是可以交换的，看第二组样例就会了解 ~

代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int p[50+2];
void dfs(int u,int ffio[52][52]) // dfs输出结果
{
    int v;
    for(v = 1; v <= 50 ; v++)
        if(ffio[u][v])
        {
            ffio[u][v]--;
            ffio[v][u]--;
            dfs(v,ffio);
            printf("%d %d\n",v,u);
        }
}
int find(int x) //连通性判断
{
    return p[x] == x ? x : find(p[x]);
}
int main()
{
#ifdef state
    freopen("sample.txt","r",stdin);
#endif
    int num,count,i,cct=1;
    int a[1000+2][3],io[50+2],ffio[50+2][50+2];
    scanf("%d",&count);
    while(count--)
    {
        int flag = 0,min = 100;
        memset(a,0,sizeof(a));
        memset(io,0,sizeof(io));
        memset(ffio,0,sizeof(ffio));
        scanf("%d",&num);
        for(i = 1; i <= 50; i++)
            p[i] = i;
        for(i = 0; i < num ; i++)
        {
            scanf("%d%d",&a[i][0],&a[i][1]);
            int p_in = a[i][0] , p_out = a[i][1];
            if(a[i][0] < min)
                min = a[i][0];
            if(a[i][1] < min)
                min = a[i][1];
            io[p_in]++;
            io[p_out]++;
            ffio[p_in][p_out]++;
            ffio[p_out][p_in]++;
            p_in=find(p_in);
            p_out=find(p_out);
            if(p_in != p_out)
                p[p_in] = p_out;
        }
        int ok = 1;
        int t = find(min);
        for( i++; i <= 50 ; i++ )
            if(io[i] && find(i) != t)
            {
                ok = 0;
                break;
            }
        if(ok)
            for( i = min; i <= 50; i++ )
                if( io[i] % 2 ) //节点度数判断
                {
                    flag = 1;
                    break;
                }
        printf("Case #%d\n",cct++);
        if(flag || !ok)
            printf("some beads may be lost\n");
        else
            dfs(min,ffio);
        if(count)
            puts("");
    }
    return 0;
}