백준 2623 c++ "음악프로그램" -[PlusUltraCode]

https://www.acmicpc.net/problem/2623

2623번: 음악프로그램

[필자 사고]

위상정렬 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다.

 

다만 이 문제의 특이한 점은 위상정렬 입력값들이 잘못 됬을때 과연 이 잘못된 과정을 어떻게 찾냐가 관건이다.

 

필자는 하나하나 연필로 3,2 인 경우를 풀어보니 dist[]의 모든 값이 0이 되지않고 도중에 탐색을 멈추게 된다는 것을 알았다.

 

이러한 과정만 잘 알고 있으면 쉽게 해결할 수 있다.

 

[소스 코드]

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

int N, M;

vector<vector<int>> Arr;
vector<int> dist;
vector<int> path;
void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	dist.resize(N + 1, 0);
	for (int i = 0; i < M; i++) {
		int T;
		cin >> T;
		vector<int> people;
		people.resize(T);
		for (int k = 0; k < T; k++) {
			cin >> people[k];

		}
		int start = people[0];
		for (int k = 1; k < people.size(); k++) {
			Arr[start].push_back(people[k]);
			dist[people[k]]++;
			start = people[k];

		}
	}
}



void Tolophical_Sort() {
	queue<int> myQueue;
	for (int i = 1; i <= N; i++) {
		if (dist[i] == 0) {
			myQueue.push(i);
		}
	}

	while (!myQueue.empty()) {
		int nowIdx = myQueue.front();
		myQueue.pop();
		path.push_back(nowIdx);
		for (int nextIdx : Arr[nowIdx]) {
			dist[nextIdx]--;
			if (dist[nextIdx] == 0) {
				myQueue.push(nextIdx);
			}
		}
	}
}

int main(void) {
	Input();
	Tolophical_Sort();
	if (path.size() != N) {
		cout << 0;
	}
	else {
		for (int i = 0; i < path.size(); i++) {
			cout << path[i] << '\n';
		}
	}
}