boj/2/2623.cpp at boj_subdir · 7thKsJ/boj · GitHub

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
// solved_5224kb_4ms_47958910_1815b

#include <stdio.h>
#include <queue>
using namespace std;

queue<int> qu;
int arr[1010][1010];
int to_do[1010];
int visited[1010];
int n,m;

int check(){
    printf("_______________\n");
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            printf("%d ", arr[i][j]);
        }
        puts("");
    }
    puts("");
    for(int i = 1; i <= n; i++){
        printf("%d ", to_do[i]);
    }
    puts("");
    for(int i = 1; i <= n; i++){
        printf("%d ", visited[i]);
    }
    printf("\n_______________\n");
}

int solve(){
    int temp = 0;
    for(int i = 1; i <= n; i++){
        if(to_do[i] == 0){
            qu.push(i);
        }
    }
    while(!qu.empty()){
        int fr = qu.front();
        visited[fr] = ++temp;
        qu.pop();
        for(int i = 1; i <= n; i++){
            if(arr[fr][i] && visited[i] == 0){
                to_do[i]--;
                if(to_do[i] == 0){
                    qu.push(i);
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(to_do[i] > 0){
            return 0;
        }
    }
    return 1;
}

int main (){
    scanf("%d %d", &n, &m);
    while(m--){
        int a, k, p;
        bool fi = false;
        scanf("%d", &a);
        while(a--){
            scanf("%d", &k);
            if(!fi) fi = true;
            else {
                if(arr[p][k] == 0){
                    arr[p][k] = 1;
                    to_do[k]++;
                }
            }
            p = k;
        }
    }
    int flag = solve();
    if(flag){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(visited[j] == i){
                    printf("%d\n", j);
                    break;
                }
            }
        }
    }
    else{
        printf("0");
    }
}