학생들을 키 순서대로 세우는 문제입니다.
위상 정렬 알고리즘을 이용해서 문제를 해결하였습니다.
A > B라는 입력이 여러개 주어졌을 때 학생들의 키를 큰 순서대로 나열해야합니다.
학생들간의 키 차이를 모두 알려주지 않을 수 있으므로 정답이 여러개로 나올 수가 있습니다.
벡터를 사용해서 자신보다 큰 사람들을 저장해줍니다.
그리고 단말노드(자신보다 큰 사람이 없는 노드)부터 시작해서 DFS로 탐색해주면 됩니다.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int> > v;
vector<bool> check;
vector<bool> terminal;
void dfs(int n)
{
for(int i=0; i<v[n].size(); ++i){
if(!check[v[n][i]]) {
dfs(v[n][i]);
}
}
if(!check[n]){
cout << n << " ";
check[n] = true;
}
}
int main(int argc, char *argv[])
{
int n, m;
int a, b;
cin >> n >> m;
v.resize(n+1);
check.resize(n+1);
terminal.resize(n+1, true);
for(int i=0; i<m; ++i){
cin >> a >> b;
v[b].push_back(a);
terminal[a] = false;
}
for(int i=1; i<=n; ++i){
if(terminal[i]){
dfs(i);
}
}
return 0;
}
'알고리즘' 카테고리의 다른 글
[C++] 11779번 최소비용 구하기 2 (0) | 2021.08.28 |
---|---|
[C++] 백준 11657번 타임머신 (0) | 2021.08.25 |
[C++] 백준 2533번 사회망 서비스(SNS) (0) | 2021.08.25 |
[C++] 백준 14226번 이모티콘 (0) | 2021.08.24 |
[C++] 백준 1926번 그림 (0) | 2021.08.18 |