4107 | 2023. 03. 14 15:29:38 | pyramis | Elágazás nélküli úton levő települések (50 pont) | cpp11 | Elfogadva 50/50 | 29ms | 6332 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool benne_van(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=0; i<=n; i++){
if(utak[i].size()==1)
zsakfaluk.push_back(i);
}
//for(int x : zsakfaluk){
// cout<<x<<endl;
//}
int elozo;
int aktualis;
vector<int> megoldas;
for(int x : zsakfaluk){
aktualis = utak[x][0];
elozo = x;
if(!benne_van(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(! benne_van(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 | 1816 KiB | |||
2 | Elfogadva | 0/0 | 29ms | 3876 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2264 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2324 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2552 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2724 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2940 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 2972 KiB | |||
9 | Elfogadva | 2/2 | 6ms | 3440 KiB | |||
10 | Elfogadva | 2/2 | 8ms | 3740 KiB | |||
11 | Elfogadva | 2/2 | 16ms | 4552 KiB | |||
12 | Elfogadva | 2/2 | 16ms | 4708 KiB | |||
13 | Elfogadva | 3/3 | 4ms | 3876 KiB | |||
14 | Elfogadva | 3/3 | 4ms | 4008 KiB | |||
15 | Elfogadva | 3/3 | 6ms | 4220 KiB | |||
16 | Elfogadva | 3/3 | 7ms | 4392 KiB | |||
17 | Elfogadva | 3/3 | 14ms | 5048 KiB | |||
18 | Elfogadva | 3/3 | 14ms | 5372 KiB | |||
19 | Elfogadva | 3/3 | 17ms | 5692 KiB | |||
20 | Elfogadva | 3/3 | 28ms | 6012 KiB | |||
21 | Elfogadva | 3/3 | 29ms | 6208 KiB | |||
22 | Elfogadva | 3/3 | 28ms | 6332 KiB |