258322026-03-04 21:55:09csdavidCsillagok bábeli tornyacpp17Wrong answer 15/100181ms22068 KiB
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int n, m;

struct Nyelv{
    vector<int> beszelok;
    vector<int> adj;
    vector<int> radj;
    bool bejart = false;
    int scc = 0;
};

Nyelv a[100001];
int karakter[100001];
stack<int> s;
int sccCount = 0; // Osszefuggo komponensek szama
int sccSize = 0; // Jelenlegi osszefuggo komponens merete
int maxi = 0; // Legnagyobb osszefuggo komponens merete
int biggestscc; // Legnagyobb osszefuggo komponens azonositoja

void dfs1(int x){
    a[x].bejart = 1;
    for (auto& it : a[x].adj){
        if (!a[it].bejart){
            dfs1(it);
        }
    }
    s.push(x);
}

void dfs2(int x){
    a[x].scc = sccCount;
    for (auto& it : a[x].adj){
        if (!a[it].scc){
            dfs2(it);
        }
    }
    sccSize += a[x].beszelok.size();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a[x].beszelok.push_back(i);
        karakter[i] = x;
    }

    for (int i = 1; i <= n; i++){
        int k;
        cin >> k;
        for (int j = 0; j < k; j++){
            int x;
            cin >> x;
            a[karakter[i]].adj.push_back(x);
            a[x].radj.push_back(karakter[i]);
        }
    }

    for (int i = 1; i <= m; i++){
        if (!a[i].bejart){
            dfs1(i);
        }
    }
    while (!s.empty()){
        int x = s.top();
        s.pop();
        if (!a[x].scc){
            sccSize = 0;
            sccCount++;
            dfs2(x);
            if (sccSize > maxi){
                maxi = sccSize;
                biggestscc = sccCount;
            }
        }
    }
    cout << maxi << '\n';
    for (int i = 1; i <= m; i++){
        if (a[i].scc == biggestscc){
            for (auto& it : a[i].beszelok){
                cout << it << ' ';
            }
        }
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer7ms8244 KiB
2Accepted14ms8764 KiB
subtask20/10
3Accepted8ms8244 KiB
4Accepted8ms8244 KiB
5Accepted8ms8244 KiB
6Wrong answer8ms8244 KiB
7Accepted8ms8244 KiB
8Accepted9ms8244 KiB
9Wrong answer9ms8244 KiB
10Wrong answer9ms8244 KiB
11Wrong answer8ms8252 KiB
12Wrong answer8ms8244 KiB
subtask315/15
13Accepted8ms8436 KiB
14Accepted8ms8244 KiB
15Accepted8ms8428 KiB
16Accepted8ms8244 KiB
17Accepted19ms8756 KiB
18Accepted17ms8948 KiB
19Accepted28ms9648 KiB
20Accepted27ms9648 KiB
21Accepted23ms9388 KiB
22Accepted24ms9268 KiB
23Accepted25ms9268 KiB
24Accepted23ms9452 KiB
25Accepted43ms10804 KiB
subtask40/10
26Accepted8ms8244 KiB
27Accepted8ms8476 KiB
28Accepted8ms8436 KiB
29Accepted8ms8244 KiB
30Accepted8ms8244 KiB
31Wrong answer7ms8052 KiB
32Wrong answer72ms13112 KiB
33Wrong answer146ms20540 KiB
34Accepted142ms18752 KiB
35Accepted181ms22068 KiB
subtask50/25
36Accepted8ms8244 KiB
37Accepted8ms8244 KiB
38Accepted8ms8244 KiB
39Wrong answer8ms8244 KiB
40Accepted8ms8244 KiB
41Accepted9ms8244 KiB
42Wrong answer9ms8244 KiB
43Wrong answer9ms8244 KiB
44Wrong answer8ms8252 KiB
45Wrong answer8ms8244 KiB
46Wrong answer7ms8428 KiB
47Accepted10ms8244 KiB
48Accepted19ms9268 KiB
49Wrong answer25ms10292 KiB
50Wrong answer8ms8244 KiB
51Accepted8ms8244 KiB
52Accepted7ms8148 KiB
53Accepted8ms8244 KiB
54Wrong answer7ms8244 KiB
55Accepted8ms8244 KiB
56Wrong answer9ms8244 KiB
57Wrong answer9ms8508 KiB
58Wrong answer12ms8504 KiB
59Wrong answer26ms10336 KiB
subtask60/40
60Wrong answer7ms8432 KiB
61Accepted14ms8756 KiB
62Accepted8ms8244 KiB
63Accepted8ms8244 KiB
64Accepted8ms8244 KiB
65Wrong answer8ms8244 KiB
66Accepted8ms8244 KiB
67Accepted9ms8244 KiB
68Wrong answer9ms8244 KiB
69Wrong answer9ms8244 KiB
70Wrong answer8ms8252 KiB
71Wrong answer8ms8244 KiB
72Accepted8ms8436 KiB
73Accepted8ms8244 KiB
74Accepted8ms8428 KiB
75Accepted8ms8244 KiB
76Accepted19ms8756 KiB
77Accepted17ms8948 KiB
78Accepted28ms9648 KiB
79Accepted27ms9648 KiB
80Accepted23ms9388 KiB
81Accepted24ms9268 KiB
82Accepted25ms9268 KiB
83Accepted23ms9452 KiB
84Accepted43ms10804 KiB
85Accepted8ms8244 KiB
86Accepted8ms8476 KiB
87Accepted8ms8436 KiB
88Accepted8ms8244 KiB
89Accepted8ms8244 KiB
90Wrong answer7ms8052 KiB
91Wrong answer72ms13112 KiB
92Wrong answer146ms20540 KiB
93Accepted142ms18752 KiB
94Accepted181ms22068 KiB
95Wrong answer7ms8428 KiB
96Accepted10ms8244 KiB
97Accepted19ms9268 KiB
98Wrong answer25ms10292 KiB
99Wrong answer8ms8244 KiB
100Accepted8ms8244 KiB
101Accepted7ms8148 KiB
102Accepted8ms8244 KiB
103Wrong answer7ms8244 KiB
104Accepted8ms8244 KiB
105Wrong answer9ms8244 KiB
106Wrong answer9ms8508 KiB
107Wrong answer12ms8504 KiB
108Wrong answer26ms10336 KiB
109Accepted29ms10544 KiB
110Accepted39ms11064 KiB
111Wrong answer92ms13620 KiB
112Wrong answer35ms10432 KiB
113Wrong answer20ms9272 KiB
114Accepted26ms9308 KiB
115Accepted25ms9384 KiB
116Accepted24ms9268 KiB
117Accepted23ms9268 KiB
118Wrong answer10ms8500 KiB
119Accepted26ms10644 KiB
120Wrong answer101ms13928 KiB
121Wrong answer29ms9612 KiB
122Wrong answer28ms9664 KiB
123Wrong answer128ms16860 KiB
124Wrong answer119ms14900 KiB
125Wrong answer119ms16436 KiB