2623 MusicPropram
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#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]);
}
}
}
}
}