266342026-04-04 12:13:12KristófCsillagok bábeli tornyacpp17Elfogadva 100/100287ms34176 KiB
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> root;
vector<vector<int>> adj;
vector<int> tin;
vector<int> tlow;
int timer=1;
vector<int> st;
int big=0;
vector<int> tmp;
vector<int> ans;
void dfs(int s,int &n)
{
tin[s]=tlow[s]=timer++;
st.push_back(s);
for(int u:adj[s])
    {
    if(tin[u]==-1)
        {
        dfs(u,n);
        tlow[s]=min(tlow[s],tlow[u]);
        }
    else if(root[u]==-1)
        {
        tlow[s]=min(tlow[s],tin[u]);
        }
    }
if(tlow[s]==tin[s])
    {
    tmp.clear();
    int u=st.back();st.pop_back();

    while(true)
        {
        root[u]=s;
        if(u<n)
            tmp.push_back(u);
        if(u==s)break;
        u=st.back();st.pop_back();
        }
    if(tmp.size()>big)
        {
        big=tmp.size();
        ans=tmp;
        }
    }
}

int main()
{
    int n,m;cin>>n>>m;
    root.resize(n+m,-1);
    tin.resize(n+m,-1);
    tlow.resize(n+m,-1);
    adj.resize(n+m);
    vector<vector<int>> anyanyelv(m);
    vector<int> speak(n);
    for(int i=0;i<n;i++)
        {
        int x;cin>>x;
        anyanyelv[--x].push_back(i);
        speak[i]=x;
        //adj[i].push_back(speak[i]+n);
        adj[speak[i]+n].push_back(i);
        adj[i].push_back(speak[i]+n);
        }
    for(int i=0;i<n;i++)
        {
        int k;cin>>k;
        for(int j=0;j<k;j++)
            {
            int x;cin>>x;x--;
            adj[x+n].push_back(i);
            }

        }
    for(int i=0;i<n;i++)
        {
        if(tin[i]==-1)dfs(i,n);
        }
    cout<<big<<"\n";
    for(int x:ans)if(x+1<=n)cout<<x+1<<" ";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva16ms2356 KiB
subtask210/10
3Elfogadva1ms512 KiB
4Elfogadva1ms500 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva2ms584 KiB
8Elfogadva1ms316 KiB
9Elfogadva2ms316 KiB
10Elfogadva2ms316 KiB
11Elfogadva1ms316 KiB
12Elfogadva2ms316 KiB
subtask315/15
13Elfogadva2ms500 KiB
14Elfogadva2ms324 KiB
15Elfogadva2ms512 KiB
16Elfogadva2ms316 KiB
17Elfogadva39ms5344 KiB
18Elfogadva28ms4796 KiB
19Elfogadva64ms10056 KiB
20Elfogadva59ms9188 KiB
21Elfogadva57ms8928 KiB
22Elfogadva54ms8584 KiB
23Elfogadva63ms8408 KiB
24Elfogadva64ms8340 KiB
25Elfogadva111ms17204 KiB
subtask410/10
26Elfogadva1ms316 KiB
27Elfogadva1ms500 KiB
28Elfogadva1ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva85ms9996 KiB
33Elfogadva208ms24312 KiB
34Elfogadva266ms21584 KiB
35Elfogadva287ms34176 KiB
subtask525/25
36Elfogadva1ms512 KiB
37Elfogadva1ms500 KiB
38Elfogadva1ms316 KiB
39Elfogadva1ms316 KiB
40Elfogadva2ms584 KiB
41Elfogadva1ms316 KiB
42Elfogadva2ms316 KiB
43Elfogadva2ms316 KiB
44Elfogadva1ms316 KiB
45Elfogadva2ms316 KiB
46Elfogadva1ms316 KiB
47Elfogadva4ms564 KiB
48Elfogadva25ms1076 KiB
49Elfogadva41ms1564 KiB
50Elfogadva2ms508 KiB
51Elfogadva1ms380 KiB
52Elfogadva1ms316 KiB
53Elfogadva1ms316 KiB
54Elfogadva3ms564 KiB
55Elfogadva3ms564 KiB
56Elfogadva3ms564 KiB
57Elfogadva7ms564 KiB
58Elfogadva7ms748 KiB
59Elfogadva46ms1652 KiB
subtask640/40
60Elfogadva1ms512 KiB
61Elfogadva17ms2356 KiB
62Elfogadva1ms512 KiB
63Elfogadva1ms500 KiB
64Elfogadva1ms316 KiB
65Elfogadva1ms316 KiB
66Elfogadva2ms584 KiB
67Elfogadva1ms316 KiB
68Elfogadva2ms316 KiB
69Elfogadva2ms316 KiB
70Elfogadva1ms316 KiB
71Elfogadva2ms316 KiB
72Elfogadva2ms500 KiB
73Elfogadva2ms324 KiB
74Elfogadva2ms512 KiB
75Elfogadva2ms316 KiB
76Elfogadva39ms5344 KiB
77Elfogadva28ms4796 KiB
78Elfogadva64ms10056 KiB
79Elfogadva59ms9188 KiB
80Elfogadva57ms8928 KiB
81Elfogadva54ms8584 KiB
82Elfogadva63ms8408 KiB
83Elfogadva64ms8340 KiB
84Elfogadva111ms17204 KiB
85Elfogadva1ms316 KiB
86Elfogadva1ms500 KiB
87Elfogadva1ms316 KiB
88Elfogadva1ms316 KiB
89Elfogadva1ms316 KiB
90Elfogadva1ms316 KiB
91Elfogadva85ms9996 KiB
92Elfogadva208ms24312 KiB
93Elfogadva266ms21584 KiB
94Elfogadva287ms34176 KiB
95Elfogadva1ms316 KiB
96Elfogadva4ms564 KiB
97Elfogadva25ms1076 KiB
98Elfogadva41ms1564 KiB
99Elfogadva2ms508 KiB
100Elfogadva1ms380 KiB
101Elfogadva1ms316 KiB
102Elfogadva1ms316 KiB
103Elfogadva3ms564 KiB
104Elfogadva3ms564 KiB
105Elfogadva3ms564 KiB
106Elfogadva7ms564 KiB
107Elfogadva7ms748 KiB
108Elfogadva46ms1652 KiB
109Elfogadva46ms1716 KiB
110Elfogadva81ms6708 KiB
111Elfogadva174ms16872 KiB
112Elfogadva64ms9532 KiB
113Elfogadva34ms4788 KiB
114Elfogadva59ms9128 KiB
115Elfogadva57ms8984 KiB
116Elfogadva57ms8652 KiB
117Elfogadva67ms8244 KiB
118Elfogadva8ms1332 KiB
119Elfogadva41ms2216 KiB
120Elfogadva153ms13368 KiB
121Elfogadva65ms9940 KiB
122Elfogadva68ms10020 KiB
123Elfogadva187ms19252 KiB
124Elfogadva196ms17972 KiB
125Elfogadva212ms18520 KiB