72052024-01-03 14:07:32MagyarKendeSZLGHálózati biztonság (50)cpp17Wrong answer 10/50317ms62320 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>;

vector<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;

    g.resize(N + 1);

    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);
            }
        }
    }

    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 << ' ';
    }
    cout << '\n';
}
SubtaskSumTestVerdictTimeMemory
base10/50
1Accepted0/03ms1824 KiB
2Wrong answer0/0151ms33788 KiB
3Wrong answer0/23ms3408 KiB
4Wrong answer0/23ms3640 KiB
5Accepted2/23ms4024 KiB
6Wrong answer0/23ms4208 KiB
7Wrong answer0/23ms4308 KiB
8Wrong answer0/23ms4620 KiB
9Wrong answer0/23ms4492 KiB
10Accepted2/28ms6680 KiB
11Wrong answer0/24ms5500 KiB
12Wrong answer0/27ms6924 KiB
13Accepted3/34ms6052 KiB
14Wrong answer0/38ms9096 KiB
15Wrong answer0/312ms11804 KiB
16Wrong answer0/3222ms32428 KiB
17Wrong answer0/38ms10260 KiB
18Accepted3/320ms20572 KiB
19Wrong answer0/3159ms54696 KiB
20Time limit exceeded0/3317ms62320 KiB
21Wrong answer0/3186ms53416 KiB
22Wrong answer0/33ms4996 KiB