258322026-03-04 21:55:09csdavidCsillagok bábeli tornyacpp17Hibás válasz 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 << ' ';
            }
        }
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz7ms8244 KiB
2Elfogadva14ms8764 KiB
subtask20/10
3Elfogadva8ms8244 KiB
4Elfogadva8ms8244 KiB
5Elfogadva8ms8244 KiB
6Hibás válasz8ms8244 KiB
7Elfogadva8ms8244 KiB
8Elfogadva9ms8244 KiB
9Hibás válasz9ms8244 KiB
10Hibás válasz9ms8244 KiB
11Hibás válasz8ms8252 KiB
12Hibás válasz8ms8244 KiB
subtask315/15
13Elfogadva8ms8436 KiB
14Elfogadva8ms8244 KiB
15Elfogadva8ms8428 KiB
16Elfogadva8ms8244 KiB
17Elfogadva19ms8756 KiB
18Elfogadva17ms8948 KiB
19Elfogadva28ms9648 KiB
20Elfogadva27ms9648 KiB
21Elfogadva23ms9388 KiB
22Elfogadva24ms9268 KiB
23Elfogadva25ms9268 KiB
24Elfogadva23ms9452 KiB
25Elfogadva43ms10804 KiB
subtask40/10
26Elfogadva8ms8244 KiB
27Elfogadva8ms8476 KiB
28Elfogadva8ms8436 KiB
29Elfogadva8ms8244 KiB
30Elfogadva8ms8244 KiB
31Hibás válasz7ms8052 KiB
32Hibás válasz72ms13112 KiB
33Hibás válasz146ms20540 KiB
34Elfogadva142ms18752 KiB
35Elfogadva181ms22068 KiB
subtask50/25
36Elfogadva8ms8244 KiB
37Elfogadva8ms8244 KiB
38Elfogadva8ms8244 KiB
39Hibás válasz8ms8244 KiB
40Elfogadva8ms8244 KiB
41Elfogadva9ms8244 KiB
42Hibás válasz9ms8244 KiB
43Hibás válasz9ms8244 KiB
44Hibás válasz8ms8252 KiB
45Hibás válasz8ms8244 KiB
46Hibás válasz7ms8428 KiB
47Elfogadva10ms8244 KiB
48Elfogadva19ms9268 KiB
49Hibás válasz25ms10292 KiB
50Hibás válasz8ms8244 KiB
51Elfogadva8ms8244 KiB
52Elfogadva7ms8148 KiB
53Elfogadva8ms8244 KiB
54Hibás válasz7ms8244 KiB
55Elfogadva8ms8244 KiB
56Hibás válasz9ms8244 KiB
57Hibás válasz9ms8508 KiB
58Hibás válasz12ms8504 KiB
59Hibás válasz26ms10336 KiB
subtask60/40
60Hibás válasz7ms8432 KiB
61Elfogadva14ms8756 KiB
62Elfogadva8ms8244 KiB
63Elfogadva8ms8244 KiB
64Elfogadva8ms8244 KiB
65Hibás válasz8ms8244 KiB
66Elfogadva8ms8244 KiB
67Elfogadva9ms8244 KiB
68Hibás válasz9ms8244 KiB
69Hibás válasz9ms8244 KiB
70Hibás válasz8ms8252 KiB
71Hibás válasz8ms8244 KiB
72Elfogadva8ms8436 KiB
73Elfogadva8ms8244 KiB
74Elfogadva8ms8428 KiB
75Elfogadva8ms8244 KiB
76Elfogadva19ms8756 KiB
77Elfogadva17ms8948 KiB
78Elfogadva28ms9648 KiB
79Elfogadva27ms9648 KiB
80Elfogadva23ms9388 KiB
81Elfogadva24ms9268 KiB
82Elfogadva25ms9268 KiB
83Elfogadva23ms9452 KiB
84Elfogadva43ms10804 KiB
85Elfogadva8ms8244 KiB
86Elfogadva8ms8476 KiB
87Elfogadva8ms8436 KiB
88Elfogadva8ms8244 KiB
89Elfogadva8ms8244 KiB
90Hibás válasz7ms8052 KiB
91Hibás válasz72ms13112 KiB
92Hibás válasz146ms20540 KiB
93Elfogadva142ms18752 KiB
94Elfogadva181ms22068 KiB
95Hibás válasz7ms8428 KiB
96Elfogadva10ms8244 KiB
97Elfogadva19ms9268 KiB
98Hibás válasz25ms10292 KiB
99Hibás válasz8ms8244 KiB
100Elfogadva8ms8244 KiB
101Elfogadva7ms8148 KiB
102Elfogadva8ms8244 KiB
103Hibás válasz7ms8244 KiB
104Elfogadva8ms8244 KiB
105Hibás válasz9ms8244 KiB
106Hibás válasz9ms8508 KiB
107Hibás válasz12ms8504 KiB
108Hibás válasz26ms10336 KiB
109Elfogadva29ms10544 KiB
110Elfogadva39ms11064 KiB
111Hibás válasz92ms13620 KiB
112Hibás válasz35ms10432 KiB
113Hibás válasz20ms9272 KiB
114Elfogadva26ms9308 KiB
115Elfogadva25ms9384 KiB
116Elfogadva24ms9268 KiB
117Elfogadva23ms9268 KiB
118Hibás válasz10ms8500 KiB
119Elfogadva26ms10644 KiB
120Hibás válasz101ms13928 KiB
121Hibás válasz29ms9612 KiB
122Hibás válasz28ms9664 KiB
123Hibás válasz128ms16860 KiB
124Hibás válasz119ms14900 KiB
125Hibás válasz119ms16436 KiB