148782025-02-05 21:47:00feheristvanHálózati biztonság (50)python3Futási hiba 0/5016ms3260 KiB
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

def find_max_k_secure_subnetwork(int n, int m, int k, vector<pair<int, int>>& edges) {
    vector<set<int>> adj(n + 1);
    for (auto [u, v] : edges) {
        adj[u].insert(v);
        adj[v].insert(u);
    }

    set<int> active_nodes;
    vector<int> degree(n + 1);
    for (int i = 1; i <= n; ++i) {
        degree[i] = adj[i].size();
        active_nodes.insert(i);
    }

    queue<int> queue;
    for (int i = 1; i <= n; ++i) {
        if (degree[i] < k) {
            queue.push(i);
        }
    }

    while (!queue.empty()) {
        int node = queue.front();
        queue.pop();
        if (active_nodes.find(node) == active_nodes.end()) continue;
        active_nodes.erase(node);
        for (int neighbor : adj[node]) {
            if (active_nodes.find(neighbor) != active_nodes.end()) {
                degree[neighbor]--;
                if (degree[neighbor] < k) {
                    queue.push(neighbor);
                }
            }
        }
    }

    vector<int> result(active_nodes.begin(), active_nodes.end());
    sort(result.begin(), result.end());
    cout << result.size() << endl;
    for (int i : result) {
        cout << i << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].first >> edges[i].second;
    }

    find_max_k_secure_subnetwork(n, m, k, edges);
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/50
1Futási hiba0/016ms3044 KiB
2Futási hiba0/016ms3048 KiB
3Futási hiba0/214ms2864 KiB
4Futási hiba0/216ms2864 KiB
5Futási hiba0/214ms2868 KiB
6Futási hiba0/214ms2900 KiB
7Futási hiba0/216ms2976 KiB
8Futási hiba0/214ms2984 KiB
9Futási hiba0/214ms2872 KiB
10Futási hiba0/214ms3260 KiB
11Futási hiba0/216ms2876 KiB
12Futási hiba0/214ms2868 KiB
13Futási hiba0/314ms3020 KiB
14Futási hiba0/314ms2976 KiB
15Futási hiba0/316ms3064 KiB
16Futási hiba0/316ms3040 KiB
17Futási hiba0/316ms3052 KiB
18Futási hiba0/316ms2876 KiB
19Futási hiba0/314ms3060 KiB
20Futási hiba0/316ms2868 KiB
21Futási hiba0/314ms2908 KiB
22Futási hiba0/316ms3044 KiB