222182026-01-14 18:04:51TaxiradioKontroll (45)cpp17Elfogadva 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 << " ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base45/45
1Elfogadva0/01ms324 KiB
2Elfogadva0/079ms13096 KiB
3Elfogadva2/21ms592 KiB
4Elfogadva2/21ms328 KiB
5Elfogadva2/21ms328 KiB
6Elfogadva3/31ms328 KiB
7Elfogadva2/21ms328 KiB
8Elfogadva2/22ms556 KiB
9Elfogadva2/24ms680 KiB
10Elfogadva2/24ms992 KiB
11Elfogadva2/26ms1204 KiB
12Elfogadva2/23ms684 KiB
13Elfogadva2/218ms3632 KiB
14Elfogadva2/219ms3900 KiB
15Elfogadva2/241ms7576 KiB
16Elfogadva2/241ms7752 KiB
17Elfogadva2/254ms10216 KiB
18Elfogadva2/252ms9988 KiB
19Elfogadva3/367ms12608 KiB
20Elfogadva3/368ms12544 KiB
21Elfogadva3/364ms14232 KiB
22Elfogadva3/325ms5204 KiB