Uva 10054

與Uva 10029 相似，不過此題為在無向圖中找出歐拉回路，并查集确定是否連通，每個點的度數必定為偶數

#include<stdio.h>
#include<string.h>
int G[51][51];
int N;
int num_of_node;
int num_of_null;
int mark=0;
int parent[51];
int num[51];
int in[51];
int stack[100][2];
int visited[51][51];
int top=-1;
void ini()
{
    num_of_node=0;
    num_of_null=0;
    top=-1;
    for(int i=0;i<51;++i)
    {

        for(int j=0;j<51;++j)
        {
            G[i][j]=0;
            visited[i][j]=0;
        }
        num[i]=1;
        parent[i]=i;
        in[i]=0;
    }
}
void Euler(int u)
{
    for(int v=0;v<51;++v)
    {
        if(G[u][v])
        {
            G[u][v]--;
            G[v][u]--;
            Euler(v);
            stack[++top][0]=u;
            stack[top][1]=v;
        }
    }
}
int is_connected()
{
    for(int i=0;i<51;++i)
    {
        if(in[i])
        {
            num_of_node++;
        }
        if(num[i]==0)
        {
            num_of_null++;
        }
    }
    if(num_of_node==num_of_null+1)
        return 1;
    return 0;
}
int is_balanced()
{
    for(int i=0;i<51;++i)
    {
        if(in[i]%2!=0&&in[i]>0)
        {
            return 0;
        }
    }
    return 1;
}
int find(int x)
{
    if(parent[x]==x)return x;
    else
    {
        parent[x]=find(parent[x]);
    }
}
void merge(int a,int b)
{
    int t1=find(a);
    int t2=find(b);
    if(t1!=t2)
    {
        num[t1]+=num[t2];
        num[t2]=0;
        parent[t2]=t1;
    }
}
int main()
{
    int kk;
    if(scanf("%d",&N)!=EOF)
    {
        for(int i=0;i<N;++i)
        {
            ini();
            mark++;
            int c;
            scanf("%d",&c);
            for(int j=0;j<c;++j)
            {
                int a,b;
                scanf("%d%d",&a,&b);
                if(j==0)
                {
                    kk=a-1;
                }
                G[a-1][b-1]++;
                G[b-1][a-1]++;
                in[a-1]++;
                in[b-1]++;
                if(G[a-1][b-1]==1||G[b-1][a-1]==1)
                {
                    merge(a-1,b-1);
                }
            }
            /*
            printf("\nconnect: ");
            for(int i=0;i<51;++i)
            {
                printf("%d ",num[i]);
            }*//*
            if(mark!=1)
            printf("\n");*/
            printf("Case #%d\n",mark);
            if(is_connected()&&is_balanced())
            {
                Euler(kk);
                while(top!=-1)
                {
                    printf("%d %d\n",stack[top][0]+1,stack[top][1]+1);
                    top--;
                }
            }
            else
            {
                printf("some beads may be lost\n");
            }
            if(i!=N-1)
            printf("\n");

        }

    }
    return 0;
}