222462026-01-14 18:30:28algoproKontroll (45)cpp17Elfogadva 45/4574ms13620 KiB
// UUID: 488993e1-25d0-4bf8-9b69-f588976e0920
// 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/01ms500 KiB
2Elfogadva0/074ms12340 KiB
3Elfogadva2/22ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva3/31ms316 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/22ms564 KiB
9Elfogadva2/23ms564 KiB
10Elfogadva2/24ms820 KiB
11Elfogadva2/26ms1076 KiB
12Elfogadva2/22ms564 KiB
13Elfogadva2/218ms3532 KiB
14Elfogadva2/219ms3744 KiB
15Elfogadva2/237ms7420 KiB
16Elfogadva2/239ms7348 KiB
17Elfogadva2/252ms9636 KiB
18Elfogadva2/250ms9640 KiB
19Elfogadva3/365ms12052 KiB
20Elfogadva3/363ms12084 KiB
21Elfogadva3/364ms13620 KiB
22Elfogadva3/323ms4912 KiB