151822025-02-15 10:39:41PKBParti (75 pont)cpp17Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
base75/75
1Accepted0/01ms508 KiB
2Accepted0/045ms3636 KiB
3Accepted3/31ms316 KiB
4Accepted3/31ms316 KiB
5Accepted3/31ms316 KiB
6Accepted3/31ms500 KiB
7Accepted3/31ms316 KiB
8Accepted4/41ms316 KiB
9Accepted4/41ms316 KiB
10Accepted4/42ms500 KiB
11Accepted4/42ms412 KiB
12Accepted4/42ms316 KiB
13Accepted4/43ms568 KiB
14Accepted4/44ms432 KiB
15Accepted4/445ms3812 KiB
16Accepted4/454ms4284 KiB
17Accepted4/465ms5056 KiB
18Accepted4/472ms5768 KiB
19Accepted4/483ms6388 KiB
20Accepted4/492ms7228 KiB
21Accepted4/497ms7020 KiB
22Accepted4/41ms508 KiB