티스토리 뷰

학생들을 키 순서대로 세우는 문제입니다.
위상 정렬 알고리즘을 이용해서 문제를 해결하였습니다.

A > B라는 입력이 여러개 주어졌을 때 학생들의 키를 큰 순서대로 나열해야합니다.
학생들간의 키 차이를 모두 알려주지 않을 수 있으므로 정답이 여러개로 나올 수가 있습니다.

벡터를 사용해서 자신보다 큰 사람들을 저장해줍니다.
그리고 단말노드(자신보다 큰 사람이 없는 노드)부터 시작해서 DFS로 탐색해주면 됩니다.

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

vector<vector<int> > v;
vector<bool> check;
vector<bool> terminal;

void dfs(int n)
{
	for(int i=0; i<v[n].size(); ++i){
		if(!check[v[n][i]]) {
			dfs(v[n][i]);
		}
	}
	if(!check[n]){
		cout << n << " ";
		check[n] = true;
	}
}

int main(int argc, char *argv[])
{
	int n, m;
	int a, b;
	
	cin >> n >> m;
	
	v.resize(n+1);
	check.resize(n+1);
	terminal.resize(n+1, true);
	
	for(int i=0; i<m; ++i){
		cin >> a >> b;
		v[b].push_back(a);
		terminal[a] = false;
	}
	
	for(int i=1; i<=n; ++i){
		if(terminal[i]){
			dfs(i);
		}
	}	
	
	return 0;
}
728x90
댓글
댓글쓰기 폼
공지사항