93342024-02-20 14:53:54AblablablaHálózati biztonság (50)cpp17Hibás válasz 37/50157ms21548 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);
        }
    }

    if(megoldas.size() != 0){
        cout << megoldas.size() << "\n";
        for(int x : megoldas){
            cout << x + 1 << " ";
        }
        cout << "\n";
    } else{
        cout << "-1\n";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base37/50
1Elfogadva0/03ms1960 KiB
2Elfogadva0/086ms10928 KiB
3Elfogadva2/23ms2252 KiB
4Elfogadva2/23ms2464 KiB
5Elfogadva2/23ms2684 KiB
6Hibás válasz0/23ms2900 KiB
7Elfogadva2/23ms2992 KiB
8Elfogadva2/23ms3000 KiB
9Hibás válasz0/23ms3212 KiB
10Elfogadva2/28ms3764 KiB
11Elfogadva2/24ms3460 KiB
12Elfogadva2/27ms4012 KiB
13Elfogadva3/33ms3720 KiB
14Elfogadva3/37ms4816 KiB
15Elfogadva3/38ms6056 KiB
16Hibás válasz0/383ms10112 KiB
17Hibás válasz0/38ms4820 KiB
18Elfogadva3/314ms9668 KiB
19Hibás válasz0/393ms19900 KiB
20Elfogadva3/3157ms21548 KiB
21Elfogadva3/3100ms20508 KiB
22Elfogadva3/33ms4412 KiB