Problem G 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1547/problem/G

먼저 DFS를 사용하여 모든 경로를 탐색한다.

탐색 과정에서 사이클이 시작되는 노드와 경로가 2개 이상이 되기 시작하는 노드를 찾는다.

사이클이 시작되는 노드의 경우,

경로 탐색 중에 현재 경로에 포함되어 있는 노드를 발견하는 경우로 찾을 수 있다.

경로가 2개 이상이 되기 시작하는 노드의 경우,

경로 탐색 중에 이전 경로 탐색에 이미 방문했던 노드를 발견하는 경우로 찾을 수 있다.

여기까지의 과정을 거치고 나면 사이클이 시작되는 노드와 경로가 2개 이상이 되기 시작하는 노드 2가지 종류의 노드를 찾은 상태가 된다.

이 상태에서 각 노드 번호를 index로 한 배열을 만들고 모든 값을 0으로 초기화한다.

( 아직 아무 곳도 방문하지 않은 상태로 초기화 )

3가지 경로 탐색 과정을 진행하여 답을 구한다.

1. 1번 노드를 시작으로 DFS로 모든 경로를 탐색하여

   방문한 노드 번호에 해당하는 배열의 값을 1로 변경한다.

2. 경로가 2개 이상이 되기 시작하는 노드들에서 각 노드를 시작으로 모든 경로를 탐색하여

   방문한 노드 번호에 해당하는 배열의 값을 2로 변경한다.

3. 사이클이 시작되는 노드들에서 각 노드를 시작으로 모든 경로를 탐색하여

   방문한 노드 번호에 해당하는 배열의 값을 -1로 변경한다.

위의 순서로 탐색을 진행하는 이유는,

위의 3가지 경우를 집합 개념으로 표현할 때 1번에 2번이 포함되고 2번에 3번이 포함되는 관계이기 때문이다.

예를 들면, 만약 어떤 임의의 노드가 3가지 경우에 모두 해당된다면 3번이 답이 되고 1번과 2번에 해당된다면 2번이 답이 된다.


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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <vector>
#include <map>
#include <set>
 
using namespace std;
 
class solution {
public:
 
    int n, m;
    vector<int> answer;
    vector<int> dfs;
    map<int, vector<int>> paths;
    set<int> s[2];
 
    // using DFS
    void findNodes(int node) {
 
        dfs[node] = 1;
 
        for (int next : paths[node]) {
 
            if (dfs[next] > 0)
                s[dfs[next] - 1].insert(next);
            else
                findNodes(next);
        }
 
        dfs[node] = 2;
    }
 
    // using DFS
    // type = 0 => have cycle
    // type = 2 => have one path
    // type = 3 => have more than one path
    void findAnswer(int node, int type) {
 
        answer[node] = type - 1;
 
        for (int next : paths[node]) {
 
            if (answer[next] != type - 1)
                findAnswer(next, type);
        }
    }
 
    void read() {
 
        cin >> n >> m;
        answer.assign(n + 1, 0);
        dfs.assign(n + 1, 0);
 
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            paths[a].push_back(b);
        }
 
        findNodes(1);
 
        findAnswer(1, 2);
 
        for (int node : s[1])
            findAnswer(node, 3);
 
        for (int node : s[0])
            findAnswer(node, 0);
 
        for (int i = 1; i <= n; i++)
            cout << answer[i] << " ";
        cout << endl;
    }
};
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
        solution s;
        s.read();
    }
 
    return 0;
}
cs

댓글

댓글 쓰기