백준 14567 c++

위상정렬에 대해 오래 전에 한번 풀어 봤던거 같은데 생각을 못해서 BFS로 시도해보려다 실패했다. 큐를 사용해 위상정렬을 구현하고, BFS보다 조건문이 적게 사용할 수 있는 거 같다. 다시 정리해보겠다.

참고 : https://www.youtube.com/watch?v=qzfeVeajuyc

#include <iostream>
#include <vector>
#include <queue>//위상정렬 큐 사용

using namespace std;

void input_data(vector<vector<int>> &lectures, vector <int>&in_degree)
{
	int N, M, i;
	int A, B;

	cin >> N >> M;
	lectures.resize(N + 1, vector<int>());
	in_degree.resize(N + 1, 0);
	for (i = 0; i < M; i++)
	{
		cin >> A >> B;
		lectures[A].push_back(B);
		in_degree[B]++;
	}

	//cout << "입력결과\n";
	//for (i = 0; i < lectures.size(); i++)
	//{
	//	cout << i << "번 과목 : ";
	//	for (auto temp : lectures[i])
	//	{
	//		cout << temp << " ";
	//	}
	//	cout << "\n";
	//}
	//cout << "\nin_degree\n";
	//for (int temp : in_degree)
	//{
	//	cout << temp << " ";
	//}
	//cout << "\n";

	return;
}

void find_answer(vector<vector<int>>& lectures, vector<int> &in_degree)
{
	int i, current, next;
	queue <int> q;
	vector<int> answers(in_degree.size());

	for (i = 1; i < in_degree.size(); i++)
	{
		if (in_degree[i] == 0)
		{
			q.push(i);
		}
		answers[i] = 1;
	}

	while (!q.empty())
	{
		//int size = q.size();
		//cout << "\n현재 q에 들어있는 수\n";
		//for (i = 0; i < size; i++)
		//{
		//	cout << q.front() << " ";
		//	q.push(q.front());
		//	q.pop();
		//}
		//cout << "\nanswers\n";
		//for (int temp : answers)
		//{
		//	cout << temp << " ";
		//}
		//cout << "\n";

		current = q.front();
		q.pop();
		for (i = 0; i < lectures[current].size(); i++)
		{
			next = lectures[current][i];
			in_degree[next]--;
			if (in_degree[next] == 0)
			{
				q.push(next);
				answers[next] = max(answers[next], answers[current] + 1);
			}
		}
	}
	for (i = 1; i < answers.size(); i++)
	{
		cout << answers[i] << " ";
	}
	cout << "\n";

	return;
}

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

	//위상정렬 사용
	vector<vector<int>> lectures;
	vector<int> in_degree;

	input_data(lectures, in_degree);
	find_answer(lectures, in_degree);

	return 0;
}