222182026-01-14 18:04:51TaxiradioKontroll (45)cpp17Accepted 45/4579ms14232 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

vector<vector<array<int , 2>>> g;
vector<int> w;
vector<bool> vis , vis2;
vector<vector<int>> g2;
int n; 

bool dfs(int h){
    if(h == 2*n-1)return 1;
    vis[h] = 1;
    while(w[h] < g[h].size()){
        if(!vis[g[h][w[h]][0]] && dfs(g[h][w[h]][0])){
            g[h][w[h]][1]--;
            g2[g[h][w[h]][0]].push_back(h);
            w[h]++;
            return 1;
        }
        w[h]++;
    }
    return 0;
}

void dfs2(int h){
    vis2[h] = 1;
    for(int x : g2[h]){
        if(!vis2[x])dfs2(x);
    }
}

int main() {
    cin >> n;
    g.resize(n*2);
    g2.resize(n*2);
    w.resize(n*2 , 0);
    vis.resize(n*2 , 0);
    vis2.resize(n*2 , 0);
    for(int i = 0 ; i < n-1; i++){
        int x; cin >> x;
        g[i+n].push_back({i , 1});
        for(int j = 0; j < x; j++){
            int y; cin >> y;y--;
            g[i].push_back({y+n , 1000000});
        }
    }
    /*
    for(int i = 0; i < 2*n; i++){
        for(auto [j , k] : g[i])cout << j << " ";
        cout << endl;
    }
    */
    int ans = 0;
    while(dfs(0)){
        ans++;
        vis[0] = 0;
    }
    cout << ans << endl;
    for(int i = 0; i < n*2; i++){
        for(auto [x , z] : g[i]){
            if(z > 0)g2[i].push_back(x);
        }
    }
    dfs2(0);
    //for(int i = 0; i < n*2; i++)cout << vis2[i] << endl;
    for(int i = 0; i < n; i++){
        if(vis2[i+n]==1 && vis2[i] == 0)cout << i+1 << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
base45/45
1Accepted0/01ms324 KiB
2Accepted0/079ms13096 KiB
3Accepted2/21ms592 KiB
4Accepted2/21ms328 KiB
5Accepted2/21ms328 KiB
6Accepted3/31ms328 KiB
7Accepted2/21ms328 KiB
8Accepted2/22ms556 KiB
9Accepted2/24ms680 KiB
10Accepted2/24ms992 KiB
11Accepted2/26ms1204 KiB
12Accepted2/23ms684 KiB
13Accepted2/218ms3632 KiB
14Accepted2/219ms3900 KiB
15Accepted2/241ms7576 KiB
16Accepted2/241ms7752 KiB
17Accepted2/254ms10216 KiB
18Accepted2/252ms9988 KiB
19Accepted3/367ms12608 KiB
20Accepted3/368ms12544 KiB
21Accepted3/364ms14232 KiB
22Accepted3/325ms5204 KiB