9326 2024. 02. 20 14:14:36 Ablablabla Hálózati biztonság (50) cpp17 Hibás válasz 37/50 150ms 27104 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> csucsok;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> befok(n);
    csucsok.assign(n, vector<int>());
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;

        befok[a]++;
        befok[b]++;
        csucsok[a].push_back(b);
        csucsok[b].push_back(a);
    }

    vector<vector<int>> uj(n, vector<int>());
    vector<bool> benne(n, 1);
    for(int i = 0; i < n; i++){
        if(befok[i] < k){
            benne[i] = 0;
            continue;
        }

        for(int x : csucsok[i]){
            if(befok[x] < k) continue;

            uj[i].push_back(x);
        }
    }

    queue<int> bejar;

    for(int i = 0; i < n; i++){
        befok[i] = uj[i].size();

        if(befok[i] != 0 && befok[i] < k){
            bejar.push(i);
        }
    }

    while(!bejar.empty()){
        int akt = bejar.front();
        bejar.pop();

        if(!benne[akt]) continue;

        benne[akt] = 0;

        for(int x : uj[akt]){
            if(!benne[x]) continue;

            befok[x]--;

            if(befok[x] < k){
                bejar.push(x);
            }
        }
    }

    vector<int> megoldas;
    for(int i = 0; i < n; i++){
        if(benne[i]){
            megoldas.push_back(i);
        }
    }

    cout << megoldas.size() << "\n";
    for(int x : megoldas){
        cout << x + 1 << " ";
    }
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 37/50
1 Elfogadva 0/0 3ms 1812 KiB
2 Elfogadva 0/0 82ms 12044 KiB
3 Elfogadva 2/2 3ms 3472 KiB
4 Elfogadva 2/2 3ms 3692 KiB
5 Elfogadva 2/2 3ms 3920 KiB
6 Hibás válasz 0/2 3ms 4128 KiB
7 Elfogadva 2/2 3ms 4244 KiB
8 Elfogadva 2/2 3ms 4460 KiB
9 Hibás válasz 0/2 3ms 4576 KiB
10 Elfogadva 2/2 8ms 5344 KiB
11 Elfogadva 2/2 4ms 5116 KiB
12 Elfogadva 2/2 7ms 5512 KiB
13 Elfogadva 3/3 3ms 5316 KiB
14 Elfogadva 3/3 7ms 6364 KiB
15 Elfogadva 3/3 8ms 7676 KiB
16 Hibás válasz 0/3 79ms 12716 KiB
17 Hibás válasz 0/3 8ms 7248 KiB
18 Elfogadva 3/3 13ms 12080 KiB
19 Hibás válasz 0/3 86ms 23100 KiB
20 Elfogadva 3/3 150ms 26832 KiB
21 Elfogadva 3/3 96ms 27104 KiB
22 Elfogadva 3/3 3ms 11008 KiB