9341 2024. 02. 20 16:46:08 PallanekPéter Hálózati biztonság (50) cpp17 Elfogadva 50/50 160ms 18232 KiB
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> graf(n+1);
    vector<int> db(n+1, 0);
    vector<bool> safe(n+1, true);
    for (int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        graf[u].push_back(v);
        graf[v].push_back(u);
        db[u]++;db[v]++;
    }
    queue<int> Q;
    for (int i=1;i<=n;i++){
        if (db[i]<k){
            Q.push(i);
        }
    }
    int ns = 0;
    while (!Q.empty()){
        int u = Q.front();
        Q.pop();
        if (!safe[u]) continue;
        safe[u] = false;
        ns++;
        for (int v : graf[u]){
            db[v]--;
            if (safe[v] and db[v] < k){
                Q.push(v);
            }
        }
    }
    cout << n - ns << "\n";
    for (int i=1; i<=n; i++){
        if (safe[i]) cout << i << " ";
    }
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1808 KiB
2 Elfogadva 0/0 86ms 9652 KiB
3 Elfogadva 2/2 3ms 2088 KiB
4 Elfogadva 2/2 3ms 2220 KiB
5 Elfogadva 2/2 3ms 2460 KiB
6 Elfogadva 2/2 3ms 2668 KiB
7 Elfogadva 2/2 3ms 2764 KiB
8 Elfogadva 2/2 3ms 2900 KiB
9 Elfogadva 2/2 3ms 2948 KiB
10 Elfogadva 2/2 8ms 3508 KiB
11 Elfogadva 2/2 4ms 3720 KiB
12 Elfogadva 2/2 7ms 4236 KiB
13 Elfogadva 3/3 3ms 4032 KiB
14 Elfogadva 3/3 7ms 4612 KiB
15 Elfogadva 3/3 8ms 5688 KiB
16 Elfogadva 3/3 81ms 9316 KiB
17 Elfogadva 3/3 8ms 4508 KiB
18 Elfogadva 3/3 12ms 7604 KiB
19 Elfogadva 3/3 93ms 15956 KiB
20 Elfogadva 3/3 160ms 18232 KiB
21 Elfogadva 3/3 112ms 16644 KiB
22 Elfogadva 3/3 3ms 4324 KiB