44022023-03-27 16:05:49kdbElágazás nélküli úton levő települések (50 pont)cpp17Elfogadva 50/5014ms5652 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <set>
#define ll long long
using namespace std;

ostream& operator<<(ostream& os, const set<int>& input)
{
    for (const int 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);
    }

    set<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;

                    ki.insert(j);
                    if (vec[j].size() > 2) break;
                    q.push(j);
                }
            }

        }
    }
    cout << ki.size() << "\n" << ki << "\n";
    return 0;
}
/*
8 9
1 2
1 6
2 7
1 5
3 4
4 5
5 6
6 7
8 7

*/
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1704 KiB
2Elfogadva0/014ms3712 KiB
3Elfogadva2/23ms2208 KiB
4Elfogadva2/23ms2440 KiB
5Elfogadva2/23ms2388 KiB
6Elfogadva2/23ms2512 KiB
7Elfogadva2/22ms2616 KiB
8Elfogadva2/23ms3100 KiB
9Elfogadva2/24ms3536 KiB
10Elfogadva2/24ms3708 KiB
11Elfogadva2/28ms4332 KiB
12Elfogadva2/28ms4472 KiB
13Elfogadva3/33ms3624 KiB
14Elfogadva3/34ms4004 KiB
15Elfogadva3/34ms4004 KiB
16Elfogadva3/34ms4536 KiB
17Elfogadva3/38ms4740 KiB
18Elfogadva3/38ms4780 KiB
19Elfogadva3/38ms5204 KiB
20Elfogadva3/313ms5652 KiB
21Elfogadva3/314ms5596 KiB
22Elfogadva3/314ms5596 KiB