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

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

2623번: 음악프로그램

 

풀이과정

위상 정렬 함수는 다른 문제와 동일하지만,  
입력을 받고 벡터 함수에 넣는 것이 색다른 문제였다.

위 사진처럼 수를 입력받고, 부등호에 따라 이중 반복문으로  
벡터 함수에 넣어주며 진입차수를 1씩 늘려주었다.

큐의 앞부분 now의 값을 res에 넣어주며 개수가 N개가 아닐 때는  
순서를 정하는 것이 불가능하다는 뜻이므로 0을 출력해준다.

 

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

int N, M, Mnum, x[1001];
int indegree[1001];

queue <int> q;
vector <int> v[1001];
vector <int> res;

void topologySort() {
	for (int i = 1; i <= N; i++) {
		if (indegree[i] == 0) {
			q.push(i);
		}
	}
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		res.push_back(now);

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			indegree[next]--;

			if (indegree[next] == 0) {
				q.push(next);
			}
		}
	}
}

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

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> Mnum;
		for (int j = 1; j <= Mnum; j++) {
			cin >> x[j];
		}
		for (int j = 1; j < Mnum; j++) {
			for (int k = j + 1; k <= Mnum; k++) {
				v[x[j]].push_back(x[k]);
				indegree[x[k]]++;
			}
		}
		memset(x, 0, sizeof(x));
	}
	topologySort();

	if (res.size() == N) { // 순서를 정하는 것이 가능할 때
		for (int i = 0; i < N; i++) {
			cout << res[i] << "\n";
		}
	}
	else cout << 0; // 불가능할 때
}