4106 | 2023. 03. 14 15:28:59 | Tibi23 | Elágazás nélküli úton levő települések (50 pont) | cpp11 | Elfogadva 50/50 | 28ms | 6696 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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1808 KiB | |||
2 | Elfogadva | 0/0 | 28ms | 4016 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2268 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2488 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2692 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2720 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2972 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3264 KiB | |||
9 | Elfogadva | 2/2 | 7ms | 3712 KiB | |||
10 | Elfogadva | 2/2 | 8ms | 4004 KiB | |||
11 | Elfogadva | 2/2 | 16ms | 4536 KiB | |||
12 | Elfogadva | 2/2 | 14ms | 4632 KiB | |||
13 | Elfogadva | 3/3 | 4ms | 3860 KiB | |||
14 | Elfogadva | 3/3 | 4ms | 4188 KiB | |||
15 | Elfogadva | 3/3 | 6ms | 4600 KiB | |||
16 | Elfogadva | 3/3 | 7ms | 4776 KiB | |||
17 | Elfogadva | 3/3 | 14ms | 5244 KiB | |||
18 | Elfogadva | 3/3 | 14ms | 5648 KiB | |||
19 | Elfogadva | 3/3 | 17ms | 6120 KiB | |||
20 | Elfogadva | 3/3 | 28ms | 6468 KiB | |||
21 | Elfogadva | 3/3 | 28ms | 6600 KiB | |||
22 | Elfogadva | 3/3 | 28ms | 6696 KiB |