DFS

https://vjudge.net/problem/UVA-10054
题意：n个珠子，每个珠子的两半由不同的颜色组成。 只有相同的颜色才能接在一起， 问能否组成一个一个项链。
题解：如果将一个珠子看成是一条连接两个顶点的无向边，那么本题就变成了求无向图是否存在欧拉回路。 对于无向图， 如果所有点的度数都是偶数并且图是联通的， 那么就存在欧拉回路。 那么从任意一个点开始走都将走完所有道路并回到起点。判联通图用并查集。

#include<string.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
using namespace std;
int degree[55],G[55][55];
int father[55],grade[55];
void DFS(int v)
{
    for(int i=1;i<=50;i++)
    {
        if(G[v][i])
        {
            G[v][i]--;
            G[i][v]--;
            DFS(i);
            printf("%d %d\n",i,v);
        }
    }
}
int parent(int v)
{
    while(v!=father[v])
    {
        father[v]=father[father[v]];
        v=father[v];
    }
    return v;
}
void  connect(int a,int b)
{

    int fa=parent(a);
    int fb=parent(b);
    if(fa==fb) return ;
    if(grade[fa]<grade[fb])
    {
        father[fb]=fa;
        grade[fa]+=grade[fb];

    }
    else
    {
        father[fa]=fb;
        grade[fb]+=grade[fa];
    }
}
int main(){
   int t,n,a,b,st;
   bool flag;
   scanf("%d",&t);
   for(int k=1;k<=t;k++)
   {
       memset(G,0,sizeof(G));
       scanf("%d",&n);
       flag=false;
       memset(degree,0,sizeof(degree));
        memset(grade,-1,sizeof(grade));
       for(int i=0;i<n;i++)
       {
           scanf("%d%d",&a,&b);
           G[a][b]++;
           G[b][a]++;
           degree[a]++;
           degree[b]++;
           connect(a,b);
           st=b;
       }
       int fa=parent(st);
       for(int i=1;i<=50;i++)
       {
           if(degree[i]==0) continue;
           if(degree[i]&1||parent(i)!=fa)
           {
               flag=true;
               break;
           }
       }
       printf("Case #%d\n",k);
       if(flag)
       {
           printf("some beads may be lost\n\n");
           continue;
       }
       DFS(st);
       printf("\n");
   }
}