151212025-02-13 10:06:04BencuHálózati biztonság (50)cpp17Időlimit túllépés 48/50382ms7104 KiB
/*#include <bits/stdc++.h>

using namespace std;
int n,k;
struct Bencu {
    int apa;
    int ido;
}a[10001];

int main()
{
    ifstream f("be.in");
    cin>>n>>k;
    for (int i=2; i<=n; i++) {
        cin>>a[i].apa>>a[i].ido;
    }
    cout<<0;
    return 0;
}*/
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_N = 100000;
vector<int> adj[MAX_N + 1];
bool valid[MAX_N + 1];

void bfs(int start, int K, set<int>& component) {
    queue<int> q;
    q.push(start);
    component.insert(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int neighbor : adj[node]) {
            if (valid[neighbor] && component.find(neighbor) == component.end()) {
                component.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    for (int i = 1; i <= N; i++) {
        valid[i] = true;
    }

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Eltávolítjuk azokat a csúcsokat, amelyeknek kevesebb mint K szomszédjuk van
    queue<int> removeQueue;
    for (int i = 1; i <= N; i++) {
        if ((int)adj[i].size() < K) {
            removeQueue.push(i);
        }
    }

    while (!removeQueue.empty()) {
        int node = removeQueue.front();
        removeQueue.pop();
        valid[node] = false;

        for (int neighbor : adj[node]) {
            if (valid[neighbor]) {
                adj[neighbor].erase(remove(adj[neighbor].begin(), adj[neighbor].end(), node), adj[neighbor].end());
                if ((int)adj[neighbor].size() < K) {
                    removeQueue.push(neighbor);
                }
            }
        }
    }

    // Megkeressük a legnagyobb K-biztonságos összefüggő komponenset
    set<int> largestComponent;

    for (int i = 1; i <= N; i++) {
        if (valid[i]) {
            set<int> component;
            bfs(i, K, component);

            if (component.size() > largestComponent.size()) {
                largestComponent = component;
            }
        }
    }

    // Kiírjuk az eredményt
    cout << largestComponent.size() << endl;
    for (int node : largestComponent) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base48/50
1Elfogadva0/03ms2612 KiB
2Elfogadva0/094ms5172 KiB
3Elfogadva2/24ms2612 KiB
4Elfogadva2/24ms2612 KiB
5Elfogadva2/26ms2612 KiB
6Elfogadva2/23ms2612 KiB
7Elfogadva2/23ms2612 KiB
8Elfogadva2/23ms2808 KiB
9Elfogadva2/23ms2804 KiB
10Időlimit túllépés0/2382ms2952 KiB
11Elfogadva2/28ms2612 KiB
12Elfogadva2/237ms2880 KiB
13Elfogadva3/34ms2612 KiB
14Elfogadva3/38ms2868 KiB
15Elfogadva3/310ms2960 KiB
16Elfogadva3/392ms4712 KiB
17Elfogadva3/38ms2868 KiB
18Elfogadva3/341ms3352 KiB
19Elfogadva3/394ms5940 KiB
20Elfogadva3/3171ms7104 KiB
21Elfogadva3/3239ms6204 KiB
22Elfogadva3/33ms2612 KiB