4649 2023. 03. 30 14:13:40 hackemon Hálózati biztonság (50) cpp17 Elfogadva 50/50 155ms 17824 KiB
#include <bits/stdc++.h>
using namespace std;


vector<vector<int>> l(100005);
vector<int> ki(100005,0);
vector<bool> rossz(100005, 0);
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    for(int i = 1;i<=m;i++ ) {
        int a, b;
        cin >> a >> b;
        l[a].push_back(b);
        l[b].push_back(a);
        ki[a]++;
        ki[b]++;
    }
    queue<int> rosszpontok;

    for(int i = 1;i<=n;i++ ) {
        if(ki[i] < k) {
            rosszpontok.push(i);
            rossz[i] = 1;
        }
    }
    while(!rosszpontok.empty()) {
        int x = rosszpontok.front();
        rosszpontok.pop();
        for(int i : l[x]) {
            if(ki[i] - 1 < k && !rossz[i]) {
                rosszpontok.push(i);
                rossz[i] = 1;
            } else {
                ki[i]--;
            }
        }
    }
    vector<int> pontok;
    for(int i = 1;i <= n;i++ ) {
        if(!rossz[i]) pontok.push_back(i);
    }
    cout << pontok.size() << endl;
    for(int i : pontok) cout << i << ' ';
    cout << endl;
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 4ms 7260 KiB
2 Elfogadva 0/0 85ms 12004 KiB
3 Elfogadva 2/2 4ms 7944 KiB
4 Elfogadva 2/2 4ms 8104 KiB
5 Elfogadva 2/2 4ms 8196 KiB
6 Elfogadva 2/2 4ms 8392 KiB
7 Elfogadva 2/2 4ms 8696 KiB
8 Elfogadva 2/2 4ms 8904 KiB
9 Elfogadva 2/2 4ms 8992 KiB
10 Elfogadva 2/2 9ms 9112 KiB
11 Elfogadva 2/2 4ms 8884 KiB
12 Elfogadva 2/2 8ms 9024 KiB
13 Elfogadva 3/3 4ms 9024 KiB
14 Elfogadva 3/3 8ms 9280 KiB
15 Elfogadva 3/3 10ms 9736 KiB
16 Elfogadva 3/3 81ms 12984 KiB
17 Elfogadva 3/3 9ms 9536 KiB
18 Elfogadva 3/3 13ms 10376 KiB
19 Elfogadva 3/3 90ms 15880 KiB
20 Elfogadva 3/3 155ms 17824 KiB
21 Elfogadva 3/3 101ms 16448 KiB
22 Elfogadva 3/3 4ms 9732 KiB