71512023-12-31 17:45:06MagyarKendeSZLGHálózati biztonság (50)cpp17Időlimit túllépés 41/50368ms63152 KiB
#include <bits/stdc++.h>

#define speed cin.tie(0); ios::sync_with_stdio(0)
#define cinv(v) for (auto& e : v) cin >> e;
#define all(v) v.begin(), v.end()
#define has(s, e) s.count(e)

using namespace std;
using ll = long long;
using point = array<int, 2>;

map<int, unordered_set<int>> g;
vector<vector<int>> groupS;
vector<bool> vis;

void dfs(int n) {
    vis[n] = 1;
    groupS.back().push_back(n);
    for (int neigh : g[n]) {
        if (!vis[neigh]) {
            dfs(neigh);
        }
    }
}

int main() {
    speed;

    int N, M, K;
    cin >> N >> M >> K;


    while (M--) {
        int U, V;
        cin >> U >> V;
        g[U].insert(V);
        g[V].insert(U);
    }

    queue<int> todo;
    for (int i = 1; i <= N; i++) {
        if (g[i].size() < K) {
            todo.push(i);
        }
    }

    while (!todo.empty()) {
        int next = todo.front(); todo.pop();
        for (int neigh : g[next]) {
            g[neigh].erase(next);
            if (g[neigh].size() < K) {
                todo.push(neigh);
            }
        }
        g.erase(next);
    }

    vis.resize(N + 1);

    for (int i = 1; i <= N; i++) {
        if (!vis[i]) {
            groupS.push_back({});
            dfs(i);
        }
    }

    vector<int>& mx = *max_element(all(groupS), 
    [](const vector<int>& a, const vector<int>& b){ return a.size() < b.size(); });

    cout << mx.size() << '\n';

    sort(all(mx));
    for (int n : mx) {
        cout << n << ' ';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base41/50
1Elfogadva0/03ms1892 KiB
2Elfogadva0/0264ms38312 KiB
3Elfogadva2/23ms3708 KiB
4Elfogadva2/23ms3844 KiB
5Elfogadva2/23ms3972 KiB
6Elfogadva2/23ms4248 KiB
7Elfogadva2/23ms4088 KiB
8Elfogadva2/24ms4412 KiB
9Elfogadva2/23ms4352 KiB
10Elfogadva2/29ms6456 KiB
11Elfogadva2/24ms5544 KiB
12Elfogadva2/29ms7092 KiB
13Elfogadva3/36ms6088 KiB
14Elfogadva3/317ms9980 KiB
15Elfogadva3/328ms13204 KiB
16Elfogadva3/3256ms32352 KiB
17Elfogadva3/317ms10216 KiB
18Elfogadva3/348ms23852 KiB
19Időlimit túllépés0/3368ms32744 KiB
20Futási hiba0/3241ms63152 KiB
21Időlimit túllépés0/3352ms32744 KiB
22Elfogadva3/33ms5376 KiB