[백준][2252][C++] 줄 세우기

링크

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

2252번: 줄 세우기

해설

 

위상정렬로 분류되있는 문제이긴한데 크게 중요하진 않은 것 같습니다.

 

생각보다 간단하게 해결했습니다.

 

그냥 입력을 받고 각 노드의 왼쪽에 있어야하는 노드들을 모두 저장해둡니다.

그리고 모든 노드들에 대해 DFS 를 하며 가장 왼쪽부터 차례대로 출력을 하면 됩니다.

 

코드에 모두 구현되어있습니다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<vector<int>> TABLE;
bool visit[32001];

void DFS(int _num) {
	if (visit[_num])
		return;
	visit[_num] = true;
	int now_size = TABLE[_num].size();

	for (int i = 0; i < now_size; ++i) {
		DFS(TABLE[_num][i]);
	}
	cout << _num << "\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	TABLE.resize(N + 1);
	for (int i = 0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		TABLE[b].push_back(a);
	}

	for (int i = 1; i <= N; ++i)
		DFS(i);

	return 0;
}