uva 10054 - The Necklace

点击打开链接uva 10054

思路: 欧拉回路
分析:
1 对于一个无向图来说如果这个图是一个欧拉图，那么必须满足该图是连通的并且每个点的度数都是偶数
2 题目给定n条边的无向图问我们是否是一个欧拉图，是的话输出欧拉图的一条路径
3 首先我们先判断是否所有点的度数都是偶数，然后我们去判断当前图是否是只有一个连通分支，那么这个利用并查集即可
4 如果都满足的话直接去搜索并且输出路径即可

代码:

#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 55;
int father[MAXN] , degree[MAXN];
int n , mat[MAXN][MAXN];

void init(){
    memset(mat , 0 , sizeof(mat));
    memset(degree , 0 , sizeof(degree));
    for(int i = 0 ; i < MAXN ; i++)
        father[i] = i;
}

int find(int x){
    if(x != father[x])
       father[x] = find(father[x]);
    return father[x];
}

bool isOk(){
    int root = -1;
    for(int i = 0 ; i < MAXN ; i++){
       if(degree[i]&1)
          return false;
       if(degree[i]){
          if(root == -1)
             root = find(i); 
          else{
             if(root != find(i)) 
                return false;
          } 
       }
    }
    return true;
}

void dfs(int cur){
    for(int i = 1 ; i < MAXN ; i++){
       if(mat[cur][i]){
          mat[cur][i]--;
          mat[i][cur]--;
          dfs(i);
          printf("%d %d\n" , i , cur); 
       }   
    }
}


int main(){
    int Case = 1 , T , x , y , start;
    bool isFirst = true;
    scanf("%d" , &T);
    while(T--){
         scanf("%d" , &n);
         init();
         for(int i = 0 ; i < n ; i++){
            scanf("%d%d", &x , &y); 
            start = x;
            mat[x][y]++;
            mat[y][x]++;
            degree[x]++;
            degree[y]++;
            father[find(x)] = find(y); 
         }
         if(isFirst)
            isFirst = false;
         else
            printf("\n");
         printf("Case #%d\n" , Case++);
         if(!isOk())
             printf("some beads may be lost\n");
         else
             dfs(start);
    }
    return 0;
}