글 읽기 - DFS를 통한 위상정렬 질문입니다.

his130 6년 전 0

제가 아래와 같이 위상정렬을 DFS를 이용해서 문제를 풀려고 하는데요..

우선순위큐를 쓰면 쉽게 풀리지만,

DFS같은 경우에는 어떤 조건을 더 줘야할까요..?

sort 로 항상 작은 값부터 시작하도록 하려고 하는데도

잘 안되네요...ㅠㅠ

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
vector<int> order;
bool visited[32001];
vector<vector<int>> v;
void dfs(int s)
{
	visited[s] = true;

	for (int i = 0; i < v[s].size(); i++)
	{
		int n = v[s][i];
		if (!visited[n])
		{
			dfs(n);
		}
	}

	order.push_back(s);

	return;
}
int main()
{
	cin >> N >> M;

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

	for (int i = 1; i <= N; i++)
	{
		reverse(v[i].begin(), v[i].end());
	}

	for (int i = N; i >= 1; i--)
	{
		if (!visited[i])
		{
			dfs(i);
		}
	}

	reverse(order.begin(), order.end());

	for (int i = 0; i < order.size(); i++)
	{
		printf("%d ", order[i]);
	}
	printf("\n");

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

DFS를 통한 위상정렬 질문입니다.

his130 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말