258332026-03-04 22:13:52csdavidCsillagok bábeli tornyacpp17Accepted 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 << ' ';
            }
        }
    }
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted8ms8244 KiB
2Accepted13ms8756 KiB
subtask210/10
3Accepted8ms8244 KiB
4Accepted8ms8440 KiB
5Accepted8ms8440 KiB
6Accepted8ms8244 KiB
7Accepted8ms8244 KiB
8Accepted8ms8056 KiB
9Accepted7ms8244 KiB
10Accepted7ms8072 KiB
11Accepted8ms8244 KiB
12Accepted8ms8244 KiB
subtask315/15
13Accepted8ms8244 KiB
14Accepted8ms8244 KiB
15Accepted8ms8244 KiB
16Accepted8ms8244 KiB
17Accepted21ms8756 KiB
18Accepted14ms8984 KiB
19Accepted28ms9648 KiB
20Accepted27ms9392 KiB
21Accepted26ms9392 KiB
22Accepted24ms9264 KiB
23Accepted25ms9012 KiB
24Accepted21ms9216 KiB
25Accepted41ms10816 KiB
subtask410/10
26Accepted8ms8244 KiB
27Accepted7ms8252 KiB
28Accepted8ms8244 KiB
29Accepted8ms8092 KiB
30Accepted8ms8068 KiB
31Accepted8ms8072 KiB
32Accepted52ms13032 KiB
33Accepted118ms19596 KiB
34Accepted194ms18888 KiB
35Accepted214ms22068 KiB
subtask525/25
36Accepted8ms8244 KiB
37Accepted8ms8440 KiB
38Accepted8ms8440 KiB
39Accepted8ms8244 KiB
40Accepted8ms8244 KiB
41Accepted8ms8056 KiB
42Accepted7ms8244 KiB
43Accepted7ms8072 KiB
44Accepted8ms8244 KiB
45Accepted8ms8244 KiB
46Accepted8ms8480 KiB
47Accepted10ms8244 KiB
48Accepted18ms9268 KiB
49Accepted27ms10292 KiB
50Accepted8ms8244 KiB
51Accepted8ms8244 KiB
52Accepted7ms8036 KiB
53Accepted8ms8244 KiB
54Accepted8ms8260 KiB
55Accepted8ms8208 KiB
56Accepted9ms8244 KiB
57Accepted12ms8500 KiB
58Accepted9ms8564 KiB
59Accepted28ms10292 KiB
subtask640/40
60Accepted8ms8244 KiB
61Accepted13ms8748 KiB
62Accepted8ms8244 KiB
63Accepted8ms8440 KiB
64Accepted8ms8440 KiB
65Accepted8ms8244 KiB
66Accepted8ms8244 KiB
67Accepted8ms8056 KiB
68Accepted7ms8244 KiB
69Accepted7ms8072 KiB
70Accepted8ms8244 KiB
71Accepted8ms8244 KiB
72Accepted8ms8244 KiB
73Accepted8ms8244 KiB
74Accepted8ms8244 KiB
75Accepted8ms8244 KiB
76Accepted21ms8756 KiB
77Accepted14ms8984 KiB
78Accepted28ms9648 KiB
79Accepted27ms9392 KiB
80Accepted26ms9392 KiB
81Accepted24ms9264 KiB
82Accepted25ms9012 KiB
83Accepted21ms9216 KiB
84Accepted41ms10816 KiB
85Accepted8ms8244 KiB
86Accepted7ms8252 KiB
87Accepted8ms8244 KiB
88Accepted8ms8092 KiB
89Accepted8ms8068 KiB
90Accepted8ms8072 KiB
91Accepted52ms13032 KiB
92Accepted118ms19596 KiB
93Accepted194ms18888 KiB
94Accepted214ms22068 KiB
95Accepted8ms8480 KiB
96Accepted10ms8244 KiB
97Accepted18ms9268 KiB
98Accepted27ms10292 KiB
99Accepted8ms8244 KiB
100Accepted8ms8244 KiB
101Accepted7ms8036 KiB
102Accepted8ms8244 KiB
103Accepted8ms8260 KiB
104Accepted8ms8208 KiB
105Accepted9ms8244 KiB
106Accepted12ms8500 KiB
107Accepted9ms8564 KiB
108Accepted28ms10292 KiB
109Accepted28ms10544 KiB
110Accepted39ms11060 KiB
111Accepted90ms13516 KiB
112Accepted29ms9920 KiB
113Accepted17ms9012 KiB
114Accepted26ms9308 KiB
115Accepted23ms9312 KiB
116Accepted21ms9268 KiB
117Accepted24ms9012 KiB
118Accepted9ms8260 KiB
119Accepted23ms10036 KiB
120Accepted90ms13876 KiB
121Accepted30ms9684 KiB
122Accepted29ms9564 KiB
123Accepted100ms16436 KiB
124Accepted114ms14388 KiB
125Accepted127ms15924 KiB