135642025-01-08 09:56:35Leventusz09Elágazás nélküli úton levő települések (50 pont)cpp17Hibás válasz 31/5028ms1332 KiB
#include <iostream>
#include <vector>
#include <algorithm>

#define nMax 10000

using namespace std;

vector<int> et[nMax];  // et[0] => élek a 0. vársoból/-ba
bool zsákfalvak[nMax]; 
bool ty[nMax];         // számlált városok

vector<int> ol;

void appendZsákfalvak(int index) {
	bool zsákfalu = zsákfalvak[index];
	ty[index] = 1;

	if (zsákfalu) {
		if(!ty[et[index][0]]) appendZsákfalvak(et[index][0]);

		return;
	}

	ol.push_back(index);

	if (et[index].size() == 2) {
		if(!ty[et[index][0]]) appendZsákfalvak(et[index][0]);
		if(!ty[et[index][1]]) appendZsákfalvak(et[index][1]);
	}
}

int main() {
	int N, M;
	cin >> N >> M;

	for (int i = 0, a, b; i < M; i++) {
		cin >> a >> b;
		a--; b--;
		et[a].push_back(b);
		et[b].push_back(a);
	}

	for (int i = 0; i < N; i++) {
		if (et[i].size() != 1) continue;
		zsákfalvak[i] = 1;
		appendZsákfalvak(i);
	}

	cout << ol.size() << "\n";
	sort(ol.begin(), ol.end());
	for (int& i : ol) cout << i + 1 << " ";


	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base31/50
1Elfogadva0/01ms564 KiB
2Elfogadva0/028ms1332 KiB
3Hibás válasz0/21ms564 KiB
4Elfogadva2/21ms756 KiB
5Elfogadva2/21ms564 KiB
6Hibás válasz0/21ms564 KiB
7Elfogadva2/21ms564 KiB
8Elfogadva2/23ms564 KiB
9Elfogadva2/24ms760 KiB
10Elfogadva2/27ms784 KiB
11Elfogadva2/214ms784 KiB
12Elfogadva2/214ms956 KiB
13Elfogadva3/32ms464 KiB
14Hibás válasz0/34ms796 KiB
15Hibás válasz0/34ms708 KiB
16Hibás válasz0/34ms568 KiB
17Hibás válasz0/312ms756 KiB
18Hibás válasz0/313ms924 KiB
19Elfogadva3/316ms940 KiB
20Elfogadva3/326ms1172 KiB
21Elfogadva3/328ms1124 KiB
22Elfogadva3/327ms1256 KiB