티스토리 뷰

알고리즘 관련/BOJ

BOJ)2623 음악프로그램

JASON 자손9319 2017. 1. 20. 04:45

문제: icpc.me/2623


음악프로그램의 출연 순서의 리스트가 주어졌을 때 모든 리스트를 만족시키도록 출연 순서를 출력하는 문제이다.


만약 모든 리스트를 만족할 수 없는 경우 0을 출력하면 된다.


우리는 출연 순서가 A->B->C 라면 A->B / B->C의 방향으로 간선을 연결해 준 뒤 topology를 구해줌으로서 리스트를 구할 수 있다.


이때 모든 리스트를 만족할 수 없는 경우는 사이클이 생기는 경우로서 그래프의 사이클 여부를 체크해줌으로서 확인 가능하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define MAX_N 1000
using namespace std;
int n, m, k, x, y, cycle, visited[MAX_N + 1], finish[MAX_N + 1];
vector<vector<int>>vt;
stack<int> st;
void dfs(int here) {
    visited[here] = true;
    for (auto there : vt[here]) {
        if (!visited[there])
            dfs(there);
        else if (!finish[there])
            cycle = 1;
    }
    finish[here] = true;
    st.push(here);
}
int main() {
    scanf("%d%d"&n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d"&k);
        for (int j = 0; j < k; j++) {
            if (!j)
                scanf("%d"&x);
            else {
                scanf("%d"&y);
                vt[x].push_back(y);
                x = y;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i])
            dfs(i);
    }
    if (cycle)
        printf("0\n");
    else {
        while (st.size()) {
            printf("%d\n", st.top());
            st.pop();
        }
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11983 Radio Contact  (0) 2017.01.21
BOJ)1766 문제집  (0) 2017.01.20
BOJ)2623 음악프로그램  (3) 2017.01.20
BOJ)11438 LCA 2  (0) 2017.01.19
BOJ)4386 Freckles  (0) 2017.01.19
BOJ)4343 Arctic Network  (0) 2017.01.19
댓글
  • 프로필사진 아아 안녕하세요 이 소스는 기존과 다른방법이던데 finished을 이용한 방법은 어떻게 아시게 된건가요? finished을 이용해서 사이클을 알게 되는 과정 도출이 궁굼합니다 2017.12.22 22:05
  • 프로필사진 JASON 자손9319 아 답변이 너무 늦었군요 ㅠㅠ..
    finish를 통하여 사이클을 도출하는 과정은, 사이클이 존재한다면 자기 자신으로 다시 돌아오는 경로가 있다는 아이디어에서 시작합니다.
    어떠한 정점이 finish되지 않았다는건 아직 그 정점에서 부터 시작 된 dfs가 끝나지 않음을 의미하니 끝나지 않은 정점을 발견하게 된다면 그 정점은 그 정점으로 다시 돌아오는 경로(사이클)이 존재한다고 볼 수 있습니다.
    2017.12.29 13:15 신고
  • 프로필사진 JASON 자손9319 본래 위상정렬을 할 수 있는 알고리즘은 크게 두 종류가 있으므로 http://jason9319.tistory.com/93?category=670441 를 참고하시면 감사하겠습니다. ㅎㅎ 2017.12.29 13:16 신고
댓글쓰기 폼