글 읽기 - 위상정렬을 이용해 문제를 풀고 있는데 어디에 이상이 있는지 감이 안잡히네요

kimmoon4 4년 전 0

몇개의 테스트 케이스를 제가 만들어서 넣어봤는데 맞는건 맞는데 몇가지 경우에서 계속 제가 의도한 결과와는 다르게 나오는데 어떤 방식으로 방향을 잡아야 하는지 감이 안잡힙니다.... 고수님들 도와주십쇼 ㅠㅠ

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <functional>
using namespace std;

int n, m,x,y;
vector<vector<int>> v;
int visit[32001];
priority_queue<int,vector<int>,less<int>> pq;

void dfs(int x)
{
	visit[x] = true;
	for (auto i : v[x])
	{
		if (visit[i])
			continue;
		dfs(i);
	}
	pq.push(x);
}

int main()
{
	cin >> n >> m;
	v.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		v[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!visit[i])
			dfs(i);
		while (!pq.empty())
		{
			cout << pq.top() << ' ';
			pq.pop();
		}
	}
	cout << '\n';
}

herdson 4년 전 1

dfs 위상정렬은 큐를 써서 푸는게 아닙니다!!!

https://jason9319.tistory.com/...

kimmoon4 4년 전 0

히익..... 제가 엄청난 실수를 범했네요..... 위상정렬 개념을 다시한번 봐야할것 같습니다

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

문제

문제

출처

ICPC

위상정렬을 이용해 문제를 풀고 있는데 어디에 이상이 있는지 감이 안잡히네요

kimmoon4 4년 전 0

herdson 4년 전 1

kimmoon4 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말