[C++] 백준 2252번 줄 세우기

[C++] 백준 2252번 줄 세우기

학생들을 키 순서대로 세우는 문제입니다.

위상 정렬 알고리즘을 이용해서 문제를 해결하였습니다.

A > B라는 입력이 여러개 주어졌을 때 학생들의 키를 큰 순서대로 나열해야합니다.

학생들간의 키 차이를 모두 알려주지 않을 수 있으므로 정답이 여러개로 나올 수가 있습니다.

벡터를 사용해서 자신보다 큰 사람들을 저장해줍니다.

그리고 단말노드(자신보다 큰 사람이 없는 노드)부터 시작해서 DFS로 탐색해주면 됩니다.

#include #include using namespace std; vector > v; vector check; vector terminal; void dfs(int n) { for(int i=0; i> n >> m; v.resize(n+1); check.resize(n+1); terminal.resize(n+1, true); for(int i=0; i> a >> b; v[b].push_back(a); terminal[a] = false; } for(int i=1; i<=n; ++i){ if(terminal[i]){ dfs(i); } } return 0; }

728x90

from http://j3sung.tistory.com/788 by ccl(A) rewrite - 2021-08-26 00:26:38