20442022-12-15 21:12:24kovacs.peter.18fHálózati biztonság (50)cpp11Accepted 50/5072ms17664 KiB
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<int>> neighbourS(N);
    vector<int> degreeS(N);
    while (M--) {
        int U, V;
        cin >> U >> V;
        ++degreeS[--U];
        ++degreeS[--V];
        neighbourS[U].push_back(V);
        neighbourS[V].push_back(U);
    }
    vector<bool> deletedS(N);
    queue<int> deletionS;
    for (int i = 0; i < N; i++) {
        if (degreeS[i] < K) {
            deletedS[i] = true;
            deletionS.push(i);
        }
    }
    while (!deletionS.empty()) {
        int n = deletionS.front();
        deletionS.pop();
        for (auto e : neighbourS[n]) {
            if (!deletedS[e] && --degreeS[e] < K) {
                deletedS[e] = true;
                deletionS.push(e);
            }
        }
    }
    vector<int> answerS;
    for (int i = 0; i < N; i++) {
        if (!deletedS[i]) {
            answerS.push_back(i);
        }
    }
    cout << answerS.size() << '\n';
    for (auto e : answerS) {
        cout << e + 1 << " ";
    }
    cout << '\n';
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1828 KiB
2Accepted0/039ms9272 KiB
3Accepted2/22ms2380 KiB
4Accepted2/22ms2584 KiB
5Accepted2/22ms2660 KiB
6Accepted2/22ms2692 KiB
7Accepted2/22ms2936 KiB
8Accepted2/22ms3180 KiB
9Accepted2/22ms3104 KiB
10Accepted2/24ms3436 KiB
11Accepted2/23ms3448 KiB
12Accepted2/24ms3752 KiB
13Accepted3/32ms3656 KiB
14Accepted3/34ms4308 KiB
15Accepted3/36ms5216 KiB
16Accepted3/337ms8660 KiB
17Accepted3/34ms4484 KiB
18Accepted3/37ms7784 KiB
19Accepted3/343ms15704 KiB
20Accepted3/372ms17664 KiB
21Accepted3/346ms16284 KiB
22Accepted3/32ms4232 KiB