41062023-03-14 15:28:59Tibi23Elágazás nélküli úton levő települések (50 pont)cpp11Accepted 50/5028ms6696 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool benneVan(vector<int> x, int szam){
    for (int i=0; i<x.size();i++){
        if(x[i]==szam){
            return true;
        }
    }
    return false;

}

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

    int m;
    cin>>m;

    vector<int> utak[n+1];

    int honnan, hova;
    for(int i=0; i<m; i++){
        cin>>honnan;
        cin>>hova;

        utak[honnan].push_back(hova);
        utak[hova].push_back(honnan);


    }

    vector<int> zsakfaluk;
    for(int i=1; i<=n; i++){
        if(utak[i].size()==1)
            zsakfaluk.push_back(i);
    }

    /*for(int x : zsakfaluk){
        cout<<x<<endl;
    }*/

    vector<int> megoldas;
    int aktualis,elozo;
    for(int x : zsakfaluk){
       aktualis = utak[x][0];
       elozo=x;
       if(!benneVan(megoldas,aktualis))
            megoldas.push_back(aktualis);
       while(utak[aktualis].size()==2){


        if(utak[aktualis][0]!=elozo){
            elozo=aktualis;
            aktualis=utak[aktualis][0];
        }
        else{
            elozo=aktualis;
            aktualis=utak[aktualis][1];
        }
        if(! benneVan(megoldas,aktualis))
            megoldas.push_back(aktualis);


       }

    }

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

    cout<<megoldas.size()<<endl;
    for(int x : megoldas)
        cout<<x<<" ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1808 KiB
2Accepted0/028ms4016 KiB
3Accepted2/23ms2268 KiB
4Accepted2/23ms2488 KiB
5Accepted2/23ms2692 KiB
6Accepted2/23ms2720 KiB
7Accepted2/23ms2972 KiB
8Accepted2/24ms3264 KiB
9Accepted2/27ms3712 KiB
10Accepted2/28ms4004 KiB
11Accepted2/216ms4536 KiB
12Accepted2/214ms4632 KiB
13Accepted3/34ms3860 KiB
14Accepted3/34ms4188 KiB
15Accepted3/36ms4600 KiB
16Accepted3/37ms4776 KiB
17Accepted3/314ms5244 KiB
18Accepted3/314ms5648 KiB
19Accepted3/317ms6120 KiB
20Accepted3/328ms6468 KiB
21Accepted3/328ms6600 KiB
22Accepted3/328ms6696 KiB