GroupBlog

题目大意

一个由两种颜色构成的珠子，好几个珠子做成一个项链，连接方式为颜色相同的一端相连，给你一些珠子，问是否能够成一个项梁。

分析

将一个珠子看作是由两个点连接成的边，剩下的连接操作是相同的颜色即可做边，那么就转化为了一个多重边的欧拉回路问题。

无向图是否具有欧拉通路的条件：
图连通 && 有且仅有0或者2个度数为奇数的点
有向图是否具有欧拉通路的条件：
图连通 && 除2个端点外其余点的入度等于出度（1个端点入度比出度大1,1个端点入度比出度小1）或者所有结点入度等于出度。
无向图是否具有欧拉回路的条件：
图连通 && 所有结点的度数均为偶数
有向图是否具有欧拉回路的条件：
图连通 && 所有结点入度等于出度

代码

/********************************************************************
* File Name: The_Monocycle.cpp
* Author: Sequin
* mail: Catherine199787@outlook.com
* Created Time: 三  9/13 18:06:12 2017
*************************************************************************/
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

int mmap[55][55];
int num[55];
int n;
int cas = 1;

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

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);

        memset(mmap, 0, sizeof(mmap));
        memset(num, 0, sizeof(num));
        for(int i = 0; i < n; i++) {
            int a, b;
            scanf("%d%d", &a, &b);
            mmap[a][b]++;
            mmap[b][a]++;
            num[a]++;
            num[b]++;
        }

        bool flag = true;
        int mmax = 0;
        int mi = 0;
        for(int i = 1; i <= 50; i++ ) {
            if(num[i] % 2 == 1){
                flag = 0;
                break;
            }
            else if(mmax < num[i]){
                mmax = num[i];
                mi = i;
            }
        }

        printf("Case #%d\n", cas++);
        if(flag){
            dfs(mi);
        }
        else{
            puts("some beads may be lost");
        }
        if(T > 0) {
            puts("");
        }
    }

    return 0;
}