알고리즘/BOJ
백준 2252번: 줄 세우기
대 혁
2020. 9. 19. 20:17
2252번: 줄 세우기
첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이��
www.acmicpc.net
입력으로 키를 비교한 두 학생이 주어지고 그 학생들끼리는 명확한 순서가 존재하기 때문에 위상정렬을 통해 풀 수 있는 문제였다.
학생들의 키 관계 그래프를 인접행렬로 표현했을 때 메모리초과가 되기 때문에 인접리스트로 구현하였다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool seen[32001];
vector<int> order;
vector<int> adj[32001];
int N, M;
void dfs(int here) {
seen[here] = true;
for (int i = 0; i < adj[here].size(); i++) {
int there = adj[here][i];
if (!seen[there]) dfs(there);
}
order.push_back(here);
}
vector<int> topologicalSort() {
for (int i = 1; i <= N; i++)
if (!seen[i]) dfs(i);
reverse(order.begin(), order.end());
return order;
}
int main(void) {
cin >> N >> M;
for (int i = 0; i < M; i++) {
int A, B;
cin >> A >> B;
adj[A].push_back(B);
}
vector<int> result = topologicalSort();
for (int i = 0; i < result.size(); i++)
cout << result[i] << ' ';
return 0;
}
알고리즘 200일 프로젝트 - 164 day