3953 2023. 03. 06 15:18:01 kdb Elágazás nélküli úton levő települések (50 pont) cpp17 Elfogadva 50/50 14ms 5984 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <stack>
#include <deque>
#include <map>
#define ll long long
using namespace std;

ostream& operator<<(ostream& os, const vector<int>& input)
{
    for (auto const& i : input) {
        os << i << " ";
    }
    return os;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<int>>vec(n + 1);
    vector<int>indul(n + 1);

    for (size_t i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
        indul[a]++;
        indul[b]++;
    }

    vector<int>zsak;
    for (size_t i = 1; i < n + 1; i++)
    {
        if (indul[i] == 1) zsak.push_back(i);
    }

    map<int, int>ki;
    for (int x : zsak)
    {
        vector<bool>visited(n + 1);
        queue<int>q;
        q.push(x);
        visited[x] = true;
        while (!q.empty())
        {
            int i = q.front();
            q.pop();
            for (int j : vec[i])
            {
                if (visited[j] == false)
                {
                    visited[j] = true;

                    if (ki.find(j) == ki.end()) ki[j] = 1;
                    if (vec[j].size() > 2) break;
                    q.push(j);
                }
            }

        }
    }
    cout << ki.size() << endl;
    for (auto i : ki)
    {
        cout << i.first << " ";
    }
    cout << endl;
    return 0;
}
/*
8 9
1 2
1 6
2 7
1 5
3 4
4 5
5 6
6 7
8 7

*/
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1824 KiB
2 Elfogadva 0/0 13ms 3908 KiB
3 Elfogadva 2/2 2ms 2276 KiB
4 Elfogadva 2/2 2ms 2492 KiB
5 Elfogadva 2/2 3ms 2700 KiB
6 Elfogadva 2/2 3ms 2912 KiB
7 Elfogadva 2/2 3ms 3084 KiB
8 Elfogadva 2/2 3ms 3404 KiB
9 Elfogadva 2/2 4ms 3612 KiB
10 Elfogadva 2/2 4ms 3964 KiB
11 Elfogadva 2/2 8ms 4616 KiB
12 Elfogadva 2/2 8ms 4972 KiB
13 Elfogadva 3/3 3ms 4104 KiB
14 Elfogadva 3/3 4ms 4500 KiB
15 Elfogadva 3/3 4ms 4496 KiB
16 Elfogadva 3/3 4ms 4896 KiB
17 Elfogadva 3/3 7ms 4980 KiB
18 Elfogadva 3/3 8ms 5020 KiB
19 Elfogadva 3/3 8ms 5336 KiB
20 Elfogadva 3/3 13ms 5876 KiB
21 Elfogadva 3/3 14ms 5984 KiB
22 Elfogadva 3/3 13ms 5944 KiB