UVA302 John's trip

Graph, Euler(오일러)

출처: UVA UVA302 John's trip
SOL)
정점의 디그리가 홀수면 오일러 회로는 있을 수 없으므로 탐색을 하기전에 검사를 한다.
그 후 오일러 경로를 탐색하여 출력
도로탐색의 우선순위가 있기 때문에 다음 정점을 결정할 때는
도로의 할당된 수가 작은 것부터 탐색을 한다. 그리고 현재 선택된 도로가
here지금 정점과 연결이 되어있는지도 확인을 해주어야 한다.


[-] Collapse

#include<stdio.h>
#include<cstring>
using namespace std;

struct road{
    int from;
    int to;
}roads[1995]; //도로의 정보
bool visit[1995]; //도로 방문 여부
int vidx;
int degree[45]; //정점의 디그리 수
int result[1995];
int roadNum;
int u, v, z;

void init(){
    roadNum = 0;
    vidx = 0;
    memset(degree, 0, sizeof(degree));
    memset(visit, false, sizeof(visit));
}

bool ok(){ //디그리가 홀수가 있다면 오일러 회로는 없다.
    for (int i = 0; i < 45; i++){
        if (degree[i] % 2 == 1) return false;
    }

    return true;
}
void Search(int here){ //오일러 탐색
    for (int r = 1; r <= roadNum; r++){
        if (!visit[r] && (roads[r].from == here || roads[r].to == here)){
            visit[r] = true;
            Search(roads[r].from + roads[r].to - here);
            result[vidx++] = r;
        }
    }
}
int main(){
    //freopen("input.txt", "r", stdin);
    while (true){
        scanf("%d%d", &u, &v);
        if (u == 0 && v == 0) break;
        init();
        scanf("%d", &z);
        degree[u]++;
        degree[v]++;
        roads[z].from = u;
        roads[z].to = v;
        roadNum++;
        int start = u > v ? v : u;
        while (true){
            scanf("%d%d", &u, &v);
            if (u == 0 && v == 0) break;
            scanf("%d", &z);
            degree[u]++;
            degree[v]++;
            roads[z].from = u;
            roads[z].to = v;
            roadNum++;
        }
        if (ok()){
            Search(start);
            for (int i = roadNum - 1; i > 0; i--)
                printf("%d ", result[i]);
            printf("%d\n\n", result[0]);
        }
        else
            printf("Round trip does not exist.\n\n");
    }
    return 0;
}