[문제 풀이 보고서] ural 1176 Hyperchannels

Abstract
ural 1176
오 라 회 로
 
Body
Source
http://acm.timus.ru/problem.aspx?space=1&num=1176
Description
오로라 에 게 돌아 갈 방향 도 를 정 하 다.
Solution
소권 법 을 어떻게 쓰 는 지 자꾸 잊 어 버 려 서 여기에 기록 해 주세요.
소권 법의 기본 적 인 사고방식 은 다음 과 같다.
연 결 된 그림 이 있 는 오 라 회 로 (존재 한다 고 가정) 는 여러 개의 고리 로 분해 할 수 있다.출발점 (만약 에 오 라 회 로 가 존재 한다 면 출발점 은 임 의적 인 것 일 수 있 음 을 주의 하 세 요) 부터 한 가지 경 로 를 마음대로 걸 으 면 반드시 출발점 자체 로 돌아 갈 수 있 습 니 다. 즉, 이 경 로 는 반드시 하나의 고리 일 것 입 니 다.원 그림 에서 이 고 리 를 제거 하 다.만약 에 경로 가 지나 가 는 점 에 사라 지지 않 은 가장자리 가 연결 되 어 있다 면 이 점 을 기점 으로 다른 고 리 를 찾 을 수 있 고 새로 찾 은 고 리 를 그림 에서 제거 하고 원래 의 고리 에 끼 워 넣 을 수 있 습 니 다.이 과정 으로 계속 돌아 가면 그림 의 오 라 회 로 를 찾 을 수 있다.
구체 적 으로 실현 시 DFS + 를 거 슬러 올 라 가면 된다.DFS 가 도착 한 현재 점 에 대해 서 는 나 가면 서 삭제 하고 DFS 가 나 가면 서 가리 키 는 점 을 마음대로 찾 습 니 다.현재 점 이 끝 이 없 으 면 현재 점 을 기점 으로 하 는 링 이 모두 사 라 졌 음 을 설명 하고 현재 점 을 답 서열 의 끝 에 추가 합 니 다.최종 적 으로 얻 은 답안 서열 은 DFS 서열 의 역순 으로 필요 에 따라 역순 할 수 있다.
위조 코드 는 매우 간단 하 니 직접 코드 를 보면 된다.
Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int N, S;
vector<int> adj[1010];
vector<int> path;

void dfs(int u)
{
    while (adj[u].size())
    {
        int v = adj[u].back();
        adj[u].pop_back();
        dfs(v);
    }
    path.push_back(u);
}

int main()
{
    int u, v, d;
    scanf("%d%d", &N, &S);
    for (u = 1; u <= N; ++u)
        for (v = 1; v <= N; ++v)
        {
            scanf("%d", &d);
            if (u!=v && d==0)
                adj[u].push_back(v);
        }
    dfs(S);
    reverse(path.begin(), path.end());
    for (int i = 0; i < path.size()-1; ++i)
        printf("%d %d
", path[i], path[i+1]);
    return 0;
}

Reference