POJ 1041 존 스 트 립.

나 는 이 문제 의 질 이 정말 좋다 고 생각한다.
우선, 고전적 인 오 라 회 로 문제 로 서 오 라 회 로 의 각 방면 의 지식 을 응용 해 야 한다.
게다가 위 에서 말 한 오로라 회로 의 지식 을 제외 하고 이 문제 자체 도 매우 좋 은 문제 이기 때문에 사고방식 과 간단 한 알고리즘 에 대한 유연 한 변통 이 필요 하 다.예컨대
① 문제 의 입력 방식 은 일반적인 문제 와 큰 차이 가 존재 한다. 케이스 는 스스로 통제 해 야 하고 입력 이 끝 나 는 조건 인 잎 은 평소 문제 와 다 르 기 때문에 새로운 것 을 많이 배 울 수 있다.
② 오 라 에 게 길 을 되 돌려 주 는 방식 도 일반적인 방법 에 국한 되 지 않 는 다. 예 를 들 어 이 문제 에서 길목 2 에서 길목 3 까지 여러 번 걸 을 수 있 고 같은 길 을 가지 않 으 면 된다. 모든 길 에는 자신의 번호 가 있다.전통 적 인 G [u] [v] 가 필요 로 하 는 두 개의 숫자 뿐만 아니 라 이 세 개의 숫자 를 어떻게 처리 할 것 인 가 를 고려 해 야 한다.여기 서 나 는 아무런 생각 이 없다.이것 은 uva 의 한 번 걷 고 출발점 으로 돌아 가 는 문제 와 크게 다르다.
③ 문제 의 특수 요 구 는 사전 순서 가 가장 작은 순서에 따라 각 도로 의 번 호 를 출력 해 야 한다. 그 전에 어떻게 처리 해 야 할 지 생각해 본 적 이 없 었 다. 이 제 는 스 택 에 존재 하 는 데 이 터 를 역순 으로 출력 하면 사전 순서 가 가장 작은 회 로 를 얻 을 수 있다 는 것 을 알 게 되 었 다. 첫 번 째 로 들 어 오 는 값 도 구 해 야 한다. 첫 번 째 u 는 모든 점 에서 가장 작은 것 이 어야 한다.지금 문 제 를 풀 고 새로운 것 을 배 울 수 있어 서 많은 것 을 얻 었 습 니 다 ~
코드 는 다음 과 같 습 니 다:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int nRoads,nPoints,start;
int G[50][2010];
bool vis[2010];
int count[50];
int stack[2010],top;

void init()
{
    nRoads = nPoints = top = 0;
    memset(G,0,sizeof(G));
    memset(vis,0,sizeof(vis));
    memset(count,0,sizeof(count));
}

int max(int a,int b)
{
    return a>b?a:b;
}

void euler(int u)
{
    for(int v=1; v <= nRoads; v++)
    {
        if(!vis[v]&&G[u][v])
        {
            vis[v]=true;
            euler(G[u][v]);
            stack[++top]=v;
        }
    }
}

void work()
{
    bool ok=false;
    for(int i=1; i<50; i++)
    {
        if(count[i]%2==1)
        {
            ok=true;
            break;
        }
    }
    if(ok)
        printf("Round trip does not exist.
");
    else
    {
        euler(start);
        for(int i=top; i>0; i--)
        {
            printf("%d",stack[i]);
            if(i-1)
                printf(" ");
        }
        printf("
");
    }
}

int main()
{
    int x,y,z;
    int flag=0;
    int t=0;
    init();
    while(scanf("%d%d",&x,&y)!=EOF)
    {
        t++;
        if(x==0&&y==0)
        {
            if(flag==1)
                break;
            flag=1;
            t=0;
            work();
            init();
            continue;
        }

        flag=0;
        scanf("%d",&z);
        if(t==1)
        {
            start=x>y?y:x;
        }
        nRoads = max(nRoads, z);
        nPoints = max(nPoints, max(x, y));
        G[x][z] = y;
        G[y][z] = x;
        count[x]++;
        count[y]++;
    }
    return 0;
}