언제나 처음처럼

[문제 링크]

입력으로 키를 비교한 두 학생이 주어지고 그 학생들끼리는 명확한 순서가 존재하기 때문에 위상정렬을 통해 풀 수 있는 문제였다.

학생들의 키 관계 그래프를 인접행렬로 표현했을 때 메모리초과가 되기 때문에 인접리스트로 구현하였다.

#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