728x90
반응형
링크
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
해설
위상정렬로 분류되있는 문제이긴한데 크게 중요하진 않은 것 같습니다.
생각보다 간단하게 해결했습니다.
그냥 입력을 받고 각 노드의 왼쪽에 있어야하는 노드들을 모두 저장해둡니다.
그리고 모든 노드들에 대해 DFS 를 하며 가장 왼쪽부터 차례대로 출력을 하면 됩니다.
코드에 모두 구현되어있습니다.
코드
#include <iostream> #include <vector> using namespace std; int N, M; vector<vector<int>> TABLE; bool visit[32001]; void DFS(int _num) { if (visit[_num]) return; visit[_num] = true; int now_size = TABLE[_num].size(); for (int i = 0; i < now_size; ++i) { DFS(TABLE[_num][i]); } cout << _num << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N >> M; TABLE.resize(N + 1); for (int i = 0; i < M; ++i) { int a, b; cin >> a >> b; TABLE[b].push_back(a); } for (int i = 1; i <= N; ++i) DFS(i); return 0; }
728x90
반응형
'컴퓨터공학 > 백준' 카테고리의 다른 글
| [백준][4195][C++] 친구 네트워크 (0) | 2021.07.17 |
|---|---|
| [백준][14003][C++] 가장 긴 증가하는 부분 수열 5 (0) | 2021.07.16 |
| [백준][11438][C++] LCA 2 (0) | 2021.07.14 |
| [백준][12015][C++] 가장 긴 증가하는 부분 수열 2 (0) | 2021.07.13 |
| [백준][1707][C++] 이분 그래프 (0) | 2021.07.12 |