[2252] 줄 세우기

// 2252 줄 세우기  
// topology sort
#include <bits/stdc++.h>
#define NMAX 32001
using namespace std;

int N, M; 
int s, e;
int visited[NMAX];
int inputEdgeCount[NMAX];
vector<int> ordered;
vector<int> adj[NMAX]; 

void dfs(int u){
	visited[u] = 1;
	for(int v: adj[u]){
		if (visited[v] == 0) dfs(v);
	}
	// 목적지 -> 출발지 역순으로 들어감 
	ordered.push_back(u);
}

vector<int> topologicalSort(int N){
	// 초기화
	ordered.clear();
	memset(visited, 0, sizeof(visited));
	
	vector<int> startNode;
	
	for(int i=1; i<=N; i++) {
		if(inputEdgeCount[i] == 0){
			startNode.push_back(i);
		}
	}
	for(int i: startNode){
		if(visited[i] == 0) dfs(i);
	}
	
	// 역순으로 정렬
	reverse(ordered.begin(), ordered.end());
	
	return ordered;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// N: 학생들의 번호 1 ~ 32,000 
	// M: 키를 비교한 횟수 1 ~ 100,000 
	scanf("%d %d", &N, &M);
	
	for(int i=0; i<M; i++){
		scanf("%d %d", &s, &e);
		adj[s].push_back(e);
		inputEdgeCount[e]++;
	}
	
	vector<int> result = topologicalSort(N);
	// 학생들을 앞에서부터 줄 세운 결과 출력  
	for (int i = 0; i < result.size(); i++) {
        printf("%d ", result[i]);
    }
	return 0;
}