71512023-12-31 17:45:06MagyarKendeSZLGHálózati biztonság (50)cpp17Time limit exceeded 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 << ' ';
    }
}
SubtaskSumTestVerdictTimeMemory
base41/50
1Accepted0/03ms1892 KiB
2Accepted0/0264ms38312 KiB
3Accepted2/23ms3708 KiB
4Accepted2/23ms3844 KiB
5Accepted2/23ms3972 KiB
6Accepted2/23ms4248 KiB
7Accepted2/23ms4088 KiB
8Accepted2/24ms4412 KiB
9Accepted2/23ms4352 KiB
10Accepted2/29ms6456 KiB
11Accepted2/24ms5544 KiB
12Accepted2/29ms7092 KiB
13Accepted3/36ms6088 KiB
14Accepted3/317ms9980 KiB
15Accepted3/328ms13204 KiB
16Accepted3/3256ms32352 KiB
17Accepted3/317ms10216 KiB
18Accepted3/348ms23852 KiB
19Time limit exceeded0/3368ms32744 KiB
20Runtime error0/3241ms63152 KiB
21Time limit exceeded0/3352ms32744 KiB
22Accepted3/33ms5376 KiB