4105 | 2023. 03. 14 15:28:29 | LeviR | Elágazás nélküli úton levő települések (50 pont) | cpp11 | Elfogadva 50/50 | 29ms | 5940 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=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) {
elozo = x;
aktualis = utak[x][0];
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 | 4008 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2420 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2540 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2520 KiB | |||
6 | Elfogadva | 2/2 | 3ms | 2692 KiB | |||
7 | Elfogadva | 2/2 | 3ms | 2800 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 2936 KiB | |||
9 | Elfogadva | 2/2 | 6ms | 3248 KiB | |||
10 | Elfogadva | 2/2 | 8ms | 3552 KiB | |||
11 | Elfogadva | 2/2 | 14ms | 3964 KiB | |||
12 | Elfogadva | 2/2 | 16ms | 4096 KiB | |||
13 | Elfogadva | 3/3 | 4ms | 3324 KiB | |||
14 | Elfogadva | 3/3 | 4ms | 3704 KiB | |||
15 | Elfogadva | 3/3 | 6ms | 4064 KiB | |||
16 | Elfogadva | 3/3 | 7ms | 4244 KiB | |||
17 | Elfogadva | 3/3 | 14ms | 4836 KiB | |||
18 | Elfogadva | 3/3 | 14ms | 4992 KiB | |||
19 | Elfogadva | 3/3 | 17ms | 5280 KiB | |||
20 | Elfogadva | 3/3 | 28ms | 5864 KiB | |||
21 | Elfogadva | 3/3 | 28ms | 5920 KiB | |||
22 | Elfogadva | 3/3 | 28ms | 5940 KiB |