260392026-03-13 18:18:02xxxCsillagok bábeli tornyacpp17Elfogadva 100/100389ms39764 KiB
#include <bits/stdc++.h>
using namespace std;

vector<int> a;
vector<vector<int> > adj, adj2, scc, b;
vector<bool> vis;
vector<int> topOrd;
int cnt = 0;

void dfs(int v) {
    vis[v] = 1;
    for(int u : adj[v]) {
        if(!vis[u]) {
            dfs(u);
        }
    }

    topOrd.push_back(v);
}

void dfs2(int v) {
    vis[v] = 1;
    scc[cnt].push_back(v);

    for(int u : adj2[v]) {
        if(!vis[u]) {
            dfs2(u);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    a.assign(n+1, 0);
    adj.resize(n+m+1);
    adj2.resize(n+m+1);
    b.resize(n+m+1);
    vis.assign(n+m+1, 0);
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        adj[i].push_back(n+a[i]);
        adj[n+a[i]].push_back(i);
        adj2[i].push_back(n+a[i]);
        adj2[n+a[i]].push_back(i);
    }

    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        for(int j = 1; j <= x; j++) {
            int y;
            cin >> y;
            adj[n+y].push_back(i);
            adj2[i].push_back(n+y);
        }
    }

    for(int i = 1; i <= n+m; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }

    reverse(topOrd.begin(), topOrd.end());

    /*for(int &x : topOrd) {
        cout << x << ' ';
    }*/

    //cout << endl;

    vis.assign(n+m+1, 0);

    for(int x : topOrd) {
        if (!vis[x]) {
            scc.push_back({});
            dfs2(x);
            cnt++;
        }
    }


    int mx = 0, ind;


    for(int i = 0; i < cnt; i++) {
        //cout << i << endl;
        for(int &x : scc[i]) {
            if (x <= n) {
                b[i].push_back(x);
                //cout << x << ' ' << b[i].size() << endl;
            }
        }

        if (mx < b[i].size()) {
            mx = b[i].size();
            ind = i;
        }
        //out << endl;
    }

    cout << mx << endl;
    for(int &x : b[ind]) {
        cout << x << ' ';
    }


}

RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva21ms3884 KiB
subtask210/10
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms336 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms332 KiB
8Elfogadva2ms512 KiB
9Elfogadva1ms316 KiB
10Elfogadva1ms332 KiB
11Elfogadva1ms332 KiB
12Elfogadva3ms316 KiB
subtask315/15
13Elfogadva1ms316 KiB
14Elfogadva1ms512 KiB
15Elfogadva1ms508 KiB
16Elfogadva1ms316 KiB
17Elfogadva67ms10076 KiB
18Elfogadva41ms8552 KiB
19Elfogadva81ms16672 KiB
20Elfogadva75ms16576 KiB
21Elfogadva75ms16488 KiB
22Elfogadva93ms16508 KiB
23Elfogadva89ms16348 KiB
24Elfogadva103ms16196 KiB
25Elfogadva250ms33292 KiB
subtask410/10
26Elfogadva1ms316 KiB
27Elfogadva1ms316 KiB
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms508 KiB
31Elfogadva1ms316 KiB
32Elfogadva187ms18528 KiB
33Elfogadva317ms39764 KiB
34Elfogadva389ms31396 KiB
35Elfogadva307ms39188 KiB
subtask525/25
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva1ms336 KiB
39Elfogadva1ms316 KiB
40Elfogadva1ms332 KiB
41Elfogadva2ms512 KiB
42Elfogadva1ms316 KiB
43Elfogadva1ms332 KiB
44Elfogadva1ms332 KiB
45Elfogadva3ms316 KiB
46Elfogadva1ms316 KiB
47Elfogadva4ms620 KiB
48Elfogadva29ms1704 KiB
49Elfogadva48ms2684 KiB
50Elfogadva2ms564 KiB
51Elfogadva2ms564 KiB
52Elfogadva2ms584 KiB
53Elfogadva2ms564 KiB
54Elfogadva3ms580 KiB
55Elfogadva3ms756 KiB
56Elfogadva4ms564 KiB
57Elfogadva8ms740 KiB
58Elfogadva8ms836 KiB
59Elfogadva52ms2580 KiB
subtask640/40
60Elfogadva1ms508 KiB
61Elfogadva21ms3736 KiB
62Elfogadva1ms316 KiB
63Elfogadva1ms316 KiB
64Elfogadva1ms336 KiB
65Elfogadva1ms316 KiB
66Elfogadva1ms332 KiB
67Elfogadva2ms512 KiB
68Elfogadva1ms316 KiB
69Elfogadva1ms332 KiB
70Elfogadva1ms332 KiB
71Elfogadva3ms316 KiB
72Elfogadva1ms316 KiB
73Elfogadva1ms512 KiB
74Elfogadva1ms508 KiB
75Elfogadva1ms316 KiB
76Elfogadva67ms10076 KiB
77Elfogadva41ms8552 KiB
78Elfogadva81ms16672 KiB
79Elfogadva75ms16576 KiB
80Elfogadva75ms16488 KiB
81Elfogadva93ms16508 KiB
82Elfogadva89ms16348 KiB
83Elfogadva103ms16196 KiB
84Elfogadva250ms33292 KiB
85Elfogadva1ms316 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva1ms316 KiB
89Elfogadva1ms508 KiB
90Elfogadva1ms316 KiB
91Elfogadva187ms18528 KiB
92Elfogadva317ms39764 KiB
93Elfogadva389ms31396 KiB
94Elfogadva307ms39188 KiB
95Elfogadva1ms316 KiB
96Elfogadva4ms620 KiB
97Elfogadva29ms1704 KiB
98Elfogadva48ms2684 KiB
99Elfogadva2ms564 KiB
100Elfogadva2ms564 KiB
101Elfogadva2ms584 KiB
102Elfogadva2ms564 KiB
103Elfogadva3ms580 KiB
104Elfogadva3ms756 KiB
105Elfogadva4ms564 KiB
106Elfogadva8ms740 KiB
107Elfogadva8ms836 KiB
108Elfogadva52ms2580 KiB
109Elfogadva52ms2984 KiB
110Elfogadva119ms10544 KiB
111Elfogadva330ms25816 KiB
112Elfogadva86ms16856 KiB
113Elfogadva43ms8512 KiB
114Elfogadva74ms16580 KiB
115Elfogadva75ms16356 KiB
116Elfogadva97ms16416 KiB
117Elfogadva97ms16084 KiB
118Elfogadva10ms1928 KiB
119Elfogadva50ms3864 KiB
120Elfogadva210ms24732 KiB
121Elfogadva79ms16780 KiB
122Elfogadva83ms16716 KiB
123Elfogadva280ms36424 KiB
124Elfogadva266ms33596 KiB
125Elfogadva354ms35392 KiB