76762024-01-10 12:28:33adamA lehető legkevesebb átszállás (50 pont)cpp17Runtime error 0/504ms5620 KiB
#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

int main() {
    int village_count;
    cin >> village_count;
    int road_count;
    cin >> road_count;

    vector<vector<int>> village_tree(village_count);
    vector<bool> have_been_here(village_count, false);

    for (int i = 0; i < road_count; i++) {

        int village_id;
        int destination_id;


        cin >> village_id >> destination_id;

        if (!count(village_tree[village_id - 1].begin(), village_tree[village_id - 1].end(), destination_id - 1)) {
            village_tree[village_id - 1].push_back(destination_id - 1);
        }
        if (!count(village_tree[destination_id - 1].begin(), village_tree[destination_id - 1].end(), village_id - 1)) {
            village_tree[destination_id - 1].push_back(village_id - 1);
        }

    }

    vector<int> reachable;

    for (int i = 0; i < village_count; i++) {
        if (village_tree[i].size() != 1)
            continue;
        bool stop = false;
        int prev = i;
        if (village_tree[village_tree[i][0]].size() > 2) {
            if (have_been_here[village_tree[i][0]]) continue;
            have_been_here[village_tree[i][0]] = true;
            reachable.push_back(village_tree[i][0]);
            continue;
        }
        int check = village_tree[i][0];
        have_been_here[i] = true;
        while (!stop) {
            if (have_been_here[check]) break;
            if (village_tree[check].size() > 2){
                have_been_here[check] = true;
                reachable.push_back(check);
                stop = true;
            }
            else if (village_tree[check].size() == 2) {
                reachable.push_back(check);
                have_been_here[check] = true;
                if (village_tree[check][0] == prev)
                    check = village_tree[check][1];
                else
                    check = village_tree[check][0];
            } else {
                stop = true;
                reachable.push_back(check);
                have_been_here[check] = true;
            }
        }

    }
    cout << reachable.size() << endl;

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

    for (int i = 0; i < reachable.size(); i++) {
        cout << reachable[i] + 1 << " ";
    }
    cout << endl;


    return 0;
}
SubtaskSumTestVerdictTimeMemory
base0/50
1Runtime error0/03ms1904 KiB
2Runtime error0/04ms2520 KiB
3Runtime error0/13ms2204 KiB
4Runtime error0/13ms2412 KiB
5Runtime error0/23ms2624 KiB
6Runtime error0/23ms2908 KiB
7Runtime error0/23ms3152 KiB
8Runtime error0/23ms3412 KiB
9Runtime error0/23ms3508 KiB
10Runtime error0/23ms3800 KiB
11Runtime error0/23ms3996 KiB
12Runtime error0/23ms4256 KiB
13Runtime error0/23ms4136 KiB
14Runtime error0/23ms4288 KiB
15Runtime error0/23ms4268 KiB
16Runtime error0/23ms4396 KiB
17Runtime error0/23ms4516 KiB
18Runtime error0/23ms4860 KiB
19Runtime error0/23ms4956 KiB
20Runtime error0/23ms5112 KiB
21Runtime error0/24ms5284 KiB
22Runtime error0/24ms5456 KiB
23Runtime error0/23ms5360 KiB
24Runtime error0/23ms5364 KiB
25Runtime error0/23ms5612 KiB
26Runtime error0/23ms5620 KiB
27Runtime error0/23ms5472 KiB
28Runtime error0/23ms5472 KiB