UVaOJ 10054 - The Necklace

——by A Code Rabbit

Description

양쪽 끝에 색깔이 있는 구슬 한 무더기를 입력하세요.출력을 밧줄로 묶을 수 있습니까?

Types

Date Structure::Graphs

Analysis

그림이 없는 오로라 회로를 구하려면 먼저 오로라 회로가 있는지 없는지를 판단한 후에 출력으로 돌아가면 된다.출력할 때 머리와 꼬리가 연결되어 있는 것을 주의하십시오. 조건에 부합되기만 하면 AC가 됩니다. (예를 들어 출력하지 않아도 됩니다.)

Solution

// UVaOJ 10054
// The Necklace
// by A Code Rabbit

#include <cstdio>
#include <cstring>

const int LIMITS_COLORS = 100;
const int LIMITS_BEADS = 2000;

int num_case;

struct Beads {
    int u;
    int v;
};  

Beads beads[LIMITS_BEADS];
int graph[LIMITS_COLORS][LIMITS_COLORS];
int n;

int order[LIMITS_COLORS];

bool visit[LIMITS_COLORS];
int sum;

void Process(int u, int v);

bool MatchConditions();
void Search(int pos);

void Print(int x);

int main() {
    scanf("%d", &num_case);
    for (int t = 1; t <= num_case; ++t) {
        // INIT.
        memset(graph, 0, sizeof(graph));
        memset(order, 0, sizeof(order));
        memset(visit, false, sizeof(visit));
        sum = 0;
        // Inputs.
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            int u, v;
            scanf("%d%d", &beads[i].u, &beads[i].v);
            Process(beads[i].u, beads[i].v);
        }
        // Compete the number of colors.
        int num_colors = 0;
        for (int i = 0; i < LIMITS_COLORS; ++i) {
            if (order[i]) {
                ++num_colors;
            }
        }
        // Judge whether the orders of them match conditions.
        bool exist_euler_circuit = MatchConditions();
        // Judge whether the undircected graph is connected.
        if (exist_euler_circuit) {
            for (int i = 0; i < LIMITS_COLORS; ++i) {
                if (order[i]) {
                    Search(i);
                    if (sum != num_colors) {
                        exist_euler_circuit = false;
                    }
                    break;
                }
            }
        }
        // Outputs.
        if (t > 1) {
            printf("
");
        }
        printf("Case #%d
", t);
        if (exist_euler_circuit) {
            Print(beads[0].u);
        } else {
            printf("some beads may be lost
");
        }
    }

    return 0;
}

void Process(int u, int v) {
    ++graph[u][v];
    ++graph[v][u];
    ++order[u];
    ++order[v];
}
            
bool MatchConditions() {
    for (int i = 0; i < LIMITS_COLORS; ++i) {
        if (order[i] % 2) {
            return false;
        }
    }
    return true;
}

void Search(int pos) {
    visit[pos] = true;
    ++sum;
    for (int i = 0; i < LIMITS_COLORS; ++i) {
        if (graph[pos][i] && !visit[i]) {
            Search(i);
        }
    }
}

void Print(int x) {
    for (int i = 0; i < LIMITS_COLORS; ++i) {
        if (graph[x][i]) {
            --graph[x][i];
            --graph[i][x];
            Print(i);
            printf("%d %d
", i, x);
        }
    }
}

PDF 다운로드
참고 자료: 없음