260392026-03-13 18:18:02xxxCsillagok bábeli tornyacpp17Accepted 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 << ' ';
    }


}

SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted21ms3884 KiB
subtask210/10
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms336 KiB
6Accepted1ms316 KiB
7Accepted1ms332 KiB
8Accepted2ms512 KiB
9Accepted1ms316 KiB
10Accepted1ms332 KiB
11Accepted1ms332 KiB
12Accepted3ms316 KiB
subtask315/15
13Accepted1ms316 KiB
14Accepted1ms512 KiB
15Accepted1ms508 KiB
16Accepted1ms316 KiB
17Accepted67ms10076 KiB
18Accepted41ms8552 KiB
19Accepted81ms16672 KiB
20Accepted75ms16576 KiB
21Accepted75ms16488 KiB
22Accepted93ms16508 KiB
23Accepted89ms16348 KiB
24Accepted103ms16196 KiB
25Accepted250ms33292 KiB
subtask410/10
26Accepted1ms316 KiB
27Accepted1ms316 KiB
28Accepted1ms316 KiB
29Accepted1ms316 KiB
30Accepted1ms508 KiB
31Accepted1ms316 KiB
32Accepted187ms18528 KiB
33Accepted317ms39764 KiB
34Accepted389ms31396 KiB
35Accepted307ms39188 KiB
subtask525/25
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms336 KiB
39Accepted1ms316 KiB
40Accepted1ms332 KiB
41Accepted2ms512 KiB
42Accepted1ms316 KiB
43Accepted1ms332 KiB
44Accepted1ms332 KiB
45Accepted3ms316 KiB
46Accepted1ms316 KiB
47Accepted4ms620 KiB
48Accepted29ms1704 KiB
49Accepted48ms2684 KiB
50Accepted2ms564 KiB
51Accepted2ms564 KiB
52Accepted2ms584 KiB
53Accepted2ms564 KiB
54Accepted3ms580 KiB
55Accepted3ms756 KiB
56Accepted4ms564 KiB
57Accepted8ms740 KiB
58Accepted8ms836 KiB
59Accepted52ms2580 KiB
subtask640/40
60Accepted1ms508 KiB
61Accepted21ms3736 KiB
62Accepted1ms316 KiB
63Accepted1ms316 KiB
64Accepted1ms336 KiB
65Accepted1ms316 KiB
66Accepted1ms332 KiB
67Accepted2ms512 KiB
68Accepted1ms316 KiB
69Accepted1ms332 KiB
70Accepted1ms332 KiB
71Accepted3ms316 KiB
72Accepted1ms316 KiB
73Accepted1ms512 KiB
74Accepted1ms508 KiB
75Accepted1ms316 KiB
76Accepted67ms10076 KiB
77Accepted41ms8552 KiB
78Accepted81ms16672 KiB
79Accepted75ms16576 KiB
80Accepted75ms16488 KiB
81Accepted93ms16508 KiB
82Accepted89ms16348 KiB
83Accepted103ms16196 KiB
84Accepted250ms33292 KiB
85Accepted1ms316 KiB
86Accepted1ms316 KiB
87Accepted1ms316 KiB
88Accepted1ms316 KiB
89Accepted1ms508 KiB
90Accepted1ms316 KiB
91Accepted187ms18528 KiB
92Accepted317ms39764 KiB
93Accepted389ms31396 KiB
94Accepted307ms39188 KiB
95Accepted1ms316 KiB
96Accepted4ms620 KiB
97Accepted29ms1704 KiB
98Accepted48ms2684 KiB
99Accepted2ms564 KiB
100Accepted2ms564 KiB
101Accepted2ms584 KiB
102Accepted2ms564 KiB
103Accepted3ms580 KiB
104Accepted3ms756 KiB
105Accepted4ms564 KiB
106Accepted8ms740 KiB
107Accepted8ms836 KiB
108Accepted52ms2580 KiB
109Accepted52ms2984 KiB
110Accepted119ms10544 KiB
111Accepted330ms25816 KiB
112Accepted86ms16856 KiB
113Accepted43ms8512 KiB
114Accepted74ms16580 KiB
115Accepted75ms16356 KiB
116Accepted97ms16416 KiB
117Accepted97ms16084 KiB
118Accepted10ms1928 KiB
119Accepted50ms3864 KiB
120Accepted210ms24732 KiB
121Accepted79ms16780 KiB
122Accepted83ms16716 KiB
123Accepted280ms36424 KiB
124Accepted266ms33596 KiB
125Accepted354ms35392 KiB