BOJ 2252 | 줄 세우기

처음 봤을 때는 그리디인가? 싶어서 몇 가지 따져봤는데 (l, r)에서 r이 움직여야 하는지 l이 움직여야 하는지 판단할 수 없는 때가 생겼다.

그래서 그래프 문제라고 생각했고 위상 정렬을 구현해서 맞았다.

코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define FASTIO ios_base::sync_with_stdio;cin.tie(nullptr);cout.tie(nullptr);

#define debug if constexpr (local) std::cout
#define endl '\n'

int visited[32001];

vector<int> graph[100001];
int isRnode[100001];

vector<int> ans;

void dfs(int node){
	visited[node] = 1;
	for (auto &i: graph[node]){
		if (!visited[i]){
			dfs(i);
		}
	}
	ans.push_back(node);
}

int main(){
	FASTIO;
	
	int N, M; cin >> N >> M;
	
	for (int i = 0; i < M; i++){
		int l, r; cin >> l >> r;
		graph[l].push_back(r);

	}
	
	for (int i = 1; i <= N; i++){
		if (!visited[i]){
			dfs(i);
		}
	}
	
	reverse(ans.begin(), ans.end());
	for (auto &i: ans) cout << i << ' ';
	cout << endl;
	
}