글 읽기 - 1766 문제집 위상정렬 문제 질문좀요 ㅠㅠㅠ

akwk777 4년 전 0

큐를 이용하려다 큐를 안이용해도 될거같아서 이렇게 풀어봤는데 왜 안되는걸까요 ㅠㅠ

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> ret;
vector<int> degree;				// 먼저 풀어야하는 문제수
vector<int> prob[32000];		// idx를 풀고 쉽게 풀수있는 문제들
void solve(int i, int origin)
{
	sort(prob[i].begin(), prob[i].end());		// 정렬해서 난이도 낮은거부터
	for (int j = 0; j < prob[i].size(); j++)
	{
		degree[prob[i][j]]--;
		if (origin > prob[i][j] && degree[prob[i][j]] == 0)	//재귀함수 밖에서 풀던 문제보다 난이도가 더 쉬운 문제였다면
		{
			ret.push_back(prob[i][j]);

			solve(prob[i][j], origin);			//이문제를 풀었을때 쉽게 풀수있는문제 또 품
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	degree.resize(N);
	int i1, i2;
	for (int i = 0; i < M; i++)
	{
		cin >> i1 >> i2;
		degree[i2 - 1]++;
		prob[i1 - 1].push_back(i2 - 1);
	}
	
	for (int i = 0; i < N; i++)
	{
		if (degree[i] == 0)			// 먼저 풀게 없다
		{
			ret.push_back(i);
			if(prob[i].empty())		// 얘를 풀어도 쉽게 풀 수 있는 문제가 없어
				continue;
			
			solve(i, i);
		}
	}
	for (int i = 0; i < ret.size(); i++)
	{
		cout << ret[i] + 1 << " ";
	}
	cout << "\n";
}

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

문제

문제

출처

ICPC

1766 문제집 위상정렬 문제 질문좀요 ㅠㅠㅠ

akwk777 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말