[백준]2252 - 줄세우기 (DFS + 위상정렬)

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

학생의 숫자와 조건의 개수,

a 학생이 b 학생보다 앞에 있다는 조건 n개가 주어졌을때

해당 조건을 만족하는 예제를 출력하는 문제

 

3번 학생 앞에는 1번학생, 2번 학생이 있다

-> 3번 학생의 앞에 있는 모든 학생의 위치가 정해져야 3번 학생의 위치가 정해진다 (위상정렬)

-> 3번 학생의 앞에 있는 학생 목록을 v[3]에 넣고 dps 탐색

 

-> 앞에 있는 모든 학생의 위치가 정해지면 해당 학생 출력

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int visit[32222];
vector<vector<int>> v(32222);

void dps(int a) {
	for (int i = 0; i < v[a].size(); i++) {
		if (visit[v[a][i]] != 1) {
			visit[v[a][i]] = 1;
			dps(v[a][i]);
		}
	}
	cout << a << " ";
}
int main() {
	int a, b;
	cin >> a >> b;
	
	
	for (int i = 0; i < b; i++) {
		int A, B;
		cin >> A >> B;
		v[B].push_back(A);
		
	}

	for (int i = 1; i <= a; i++) {
		if (visit[i] != 1) {
			visit[i] = 1;
			dps(i);
		}

	}
}