151822025-02-15 10:39:41PKBParti (75 pont)cpp17Elfogadva 75/7597ms7228 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int N;
    cin >> N;

    vector<pair<int, int>> preferences(N);
    for (int i = 0; i < N; ++i) {
        cin >> preferences[i].first >> preferences[i].second;
    }

    vector<vector<int>> supporters(N + 1);


    for (int i = 1; i <= N; ++i) {
        int a = preferences[i - 1].first;
        int b = preferences[i - 1].second;
        supporters[a].push_back(i);
        supporters[b].push_back(i);
    }

    vector<int> support(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        support[i] = supporters[i].size();
    }

    vector<bool> invited(N + 1, true);
    queue<int> q;

    for (int i = 1; i <= N; ++i) {
        if (support[i] < 2) {
            invited[i] = false;
            q.push(i);
        }
    }

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

        int rec1 = preferences[person - 1].first;
        int rec2 = preferences[person - 1].second;

        if (invited[rec1]) {
            support[rec1]--;
            if (support[rec1] < 2) {
                invited[rec1] = false;
                q.push(rec1);
            }
        }

        if (invited[rec2]) {
            support[rec2]--;
            if (support[rec2] < 2) {
                invited[rec2] = false;
                q.push(rec2);
            }
        }
    }

    vector<int> result;
    for (int i = 1; i <= N; ++i) {
        if (invited[i])
            result.push_back(i);
    }

    sort(result.begin(), result.end());

    cout << result.size() << "\n";
    for (int person : result)
        cout << person << " ";
    cout << "\n";

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base75/75
1Elfogadva0/01ms508 KiB
2Elfogadva0/045ms3636 KiB
3Elfogadva3/31ms316 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/31ms316 KiB
6Elfogadva3/31ms500 KiB
7Elfogadva3/31ms316 KiB
8Elfogadva4/41ms316 KiB
9Elfogadva4/41ms316 KiB
10Elfogadva4/42ms500 KiB
11Elfogadva4/42ms412 KiB
12Elfogadva4/42ms316 KiB
13Elfogadva4/43ms568 KiB
14Elfogadva4/44ms432 KiB
15Elfogadva4/445ms3812 KiB
16Elfogadva4/454ms4284 KiB
17Elfogadva4/465ms5056 KiB
18Elfogadva4/472ms5768 KiB
19Elfogadva4/483ms6388 KiB
20Elfogadva4/492ms7228 KiB
21Elfogadva4/497ms7020 KiB
22Elfogadva4/41ms508 KiB