2623 MusicPropram

์ฝ”๋“œ

#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#define MAX_SINGER 1000
#define MAX_PD 100
 
using namespace std;
 
typedef struct Singer {
	int beforeCount;
	bool isCheked;
	vector<int> next;
} Singer;
 
Singer singer[MAX_SINGER];
int order[MAX_SINGER], numOfSinger;
vector<vector<int>> set;
int check[MAX_SINGER];
bool checkDup[MAX_SINGER][MAX_SINGER];
int pd[MAX_SINGER];
 
bool unionFind(int forward, int backward);
void makeOrder();
 
int main() {
	memset(check, -1, sizeof(check));
	int numOfPd;
	cin >> numOfSinger >> numOfPd;
	for (int i = 0; i < numOfPd; i++) {
		int ns;
		cin >> ns;
		for (int j = 0; j < ns; j++) {
			cin >> pd[j];
			pd[j]--;
			if (j != 0) {
				for (int k = 0; k < j; k++) {
					if (!checkDup[pd[k]][pd[j]]) {
						if (unionFind(pd[k], pd[j])) {
							singer[pd[k]].next.push_back(pd[j]);
							singer[pd[j]].beforeCount++;
							checkDup[pd[k]][pd[j]] = true;
						}
						else {
							cout << 0 << endl;
							return 0;
						}
					}
				}
			}
		}
	}
 
	makeOrder();
	for (int i = 0; i < numOfSinger; i++)
		cout << order[i] + 1 << endl;
}
 
bool unionFind(int forward, int backward) {
	if (check[forward] == -1 && check[backward] == -1) {
		vector<int> temp;
		temp.push_back(forward);
		temp.push_back(backward);
		set.push_back(temp);
		check[forward] = set.size() - 1;
		check[backward] = set.size() - 1;
	}
	else if (check[forward] == -1) {
		set[check[backward]].push_back(forward);
		check[forward] = check[backward];
	}
	else if (check[backward] == -1) {
		set[check[forward]].push_back(backward);
		check[backward] = check[forward];
	}
	else if (check[forward] != check[backward]) {
		for (int i = 0; i < set[check[backward]].size(); i++) {
			check[set[check[backward]][i]] = check[forward];
			set[check[forward]].push_back(set[check[backward]][i]);
		}
		set[check[backward]].clear();
	}
	else {
		return false;
	}
	return true;
}
 
void makeOrder() {
	list<int> q;
	int orderIndex = 0;
	for (int i = 0; i < numOfSinger; i++)
		if (singer[i].beforeCount == 0) {
			q.push_back(i);
			singer[i].isCheked = true;
		}
 
	while (!q.empty()) {
		int length = q.size();
		for (int i = 0; i < length; i++) {
			int temp = q.front();
			q.pop_front();
			order[orderIndex++] = temp;
			for (int j = 0; j < singer[temp].next.size(); j++) {
				singer[singer[temp].next[j]].beforeCount--;
				if (singer[singer[temp].next[j]].beforeCount == 0 && !singer[singer[temp].next[j]].isCheked) {
					singer[singer[temp].next[j]].isCheked = true;
					q.push_back(singer[temp].next[j]);
				}
			}
		}
	}
}