258332026-03-04 22:13:52csdavidCsillagok bábeli tornyacpp17Elfogadva 100/100214ms22068 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;
int sccSize = 0;
int maxi = 0;
int biggestscc;

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].radj){
        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 << ' ';
            }
        }
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva8ms8244 KiB
2Elfogadva13ms8756 KiB
subtask210/10
3Elfogadva8ms8244 KiB
4Elfogadva8ms8440 KiB
5Elfogadva8ms8440 KiB
6Elfogadva8ms8244 KiB
7Elfogadva8ms8244 KiB
8Elfogadva8ms8056 KiB
9Elfogadva7ms8244 KiB
10Elfogadva7ms8072 KiB
11Elfogadva8ms8244 KiB
12Elfogadva8ms8244 KiB
subtask315/15
13Elfogadva8ms8244 KiB
14Elfogadva8ms8244 KiB
15Elfogadva8ms8244 KiB
16Elfogadva8ms8244 KiB
17Elfogadva21ms8756 KiB
18Elfogadva14ms8984 KiB
19Elfogadva28ms9648 KiB
20Elfogadva27ms9392 KiB
21Elfogadva26ms9392 KiB
22Elfogadva24ms9264 KiB
23Elfogadva25ms9012 KiB
24Elfogadva21ms9216 KiB
25Elfogadva41ms10816 KiB
subtask410/10
26Elfogadva8ms8244 KiB
27Elfogadva7ms8252 KiB
28Elfogadva8ms8244 KiB
29Elfogadva8ms8092 KiB
30Elfogadva8ms8068 KiB
31Elfogadva8ms8072 KiB
32Elfogadva52ms13032 KiB
33Elfogadva118ms19596 KiB
34Elfogadva194ms18888 KiB
35Elfogadva214ms22068 KiB
subtask525/25
36Elfogadva8ms8244 KiB
37Elfogadva8ms8440 KiB
38Elfogadva8ms8440 KiB
39Elfogadva8ms8244 KiB
40Elfogadva8ms8244 KiB
41Elfogadva8ms8056 KiB
42Elfogadva7ms8244 KiB
43Elfogadva7ms8072 KiB
44Elfogadva8ms8244 KiB
45Elfogadva8ms8244 KiB
46Elfogadva8ms8480 KiB
47Elfogadva10ms8244 KiB
48Elfogadva18ms9268 KiB
49Elfogadva27ms10292 KiB
50Elfogadva8ms8244 KiB
51Elfogadva8ms8244 KiB
52Elfogadva7ms8036 KiB
53Elfogadva8ms8244 KiB
54Elfogadva8ms8260 KiB
55Elfogadva8ms8208 KiB
56Elfogadva9ms8244 KiB
57Elfogadva12ms8500 KiB
58Elfogadva9ms8564 KiB
59Elfogadva28ms10292 KiB
subtask640/40
60Elfogadva8ms8244 KiB
61Elfogadva13ms8748 KiB
62Elfogadva8ms8244 KiB
63Elfogadva8ms8440 KiB
64Elfogadva8ms8440 KiB
65Elfogadva8ms8244 KiB
66Elfogadva8ms8244 KiB
67Elfogadva8ms8056 KiB
68Elfogadva7ms8244 KiB
69Elfogadva7ms8072 KiB
70Elfogadva8ms8244 KiB
71Elfogadva8ms8244 KiB
72Elfogadva8ms8244 KiB
73Elfogadva8ms8244 KiB
74Elfogadva8ms8244 KiB
75Elfogadva8ms8244 KiB
76Elfogadva21ms8756 KiB
77Elfogadva14ms8984 KiB
78Elfogadva28ms9648 KiB
79Elfogadva27ms9392 KiB
80Elfogadva26ms9392 KiB
81Elfogadva24ms9264 KiB
82Elfogadva25ms9012 KiB
83Elfogadva21ms9216 KiB
84Elfogadva41ms10816 KiB
85Elfogadva8ms8244 KiB
86Elfogadva7ms8252 KiB
87Elfogadva8ms8244 KiB
88Elfogadva8ms8092 KiB
89Elfogadva8ms8068 KiB
90Elfogadva8ms8072 KiB
91Elfogadva52ms13032 KiB
92Elfogadva118ms19596 KiB
93Elfogadva194ms18888 KiB
94Elfogadva214ms22068 KiB
95Elfogadva8ms8480 KiB
96Elfogadva10ms8244 KiB
97Elfogadva18ms9268 KiB
98Elfogadva27ms10292 KiB
99Elfogadva8ms8244 KiB
100Elfogadva8ms8244 KiB
101Elfogadva7ms8036 KiB
102Elfogadva8ms8244 KiB
103Elfogadva8ms8260 KiB
104Elfogadva8ms8208 KiB
105Elfogadva9ms8244 KiB
106Elfogadva12ms8500 KiB
107Elfogadva9ms8564 KiB
108Elfogadva28ms10292 KiB
109Elfogadva28ms10544 KiB
110Elfogadva39ms11060 KiB
111Elfogadva90ms13516 KiB
112Elfogadva29ms9920 KiB
113Elfogadva17ms9012 KiB
114Elfogadva26ms9308 KiB
115Elfogadva23ms9312 KiB
116Elfogadva21ms9268 KiB
117Elfogadva24ms9012 KiB
118Elfogadva9ms8260 KiB
119Elfogadva23ms10036 KiB
120Elfogadva90ms13876 KiB
121Elfogadva30ms9684 KiB
122Elfogadva29ms9564 KiB
123Elfogadva100ms16436 KiB
124Elfogadva114ms14388 KiB
125Elfogadva127ms15924 KiB