135242025-01-08 09:23:15RRoliElágazás nélküli úton levő települések (50 pont)cpp17Elfogadva 50/5028ms1332 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, fok[10001], sor[10001];

int aux[10001];
void msort(int e1, int u2) {
	int u1 = (e1+u2)/2, e2 = u1+1;
	if(e1 != u1) msort(e1, u1);
	if(e2 != u2) msort(e2, u2);
	int l = e1, r = e2, p = e1;
	while(p <= u2) {
		if(r > u2 || (sor[l] <= sor[r] && l <= u1)) {
			aux[p] = sor[l];
			l++;
		} else {
			aux[p] = sor[r];
			r++;
		}
		p++;
	}
	for(int i = e1; i <= u2; i++) sor[i] = aux[i];
}

int main() {
	cin >> n >> m;
	vector<vector<int>> szom(n+1, vector<int>(0));
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		szom[a].push_back(b);
		szom[b].push_back(a);
		fok[a]++;
		fok[b]++;
	}

	int e = 0, u = 0, kezd = 0, L[10001];
	bool tovabb[10001];

	for(int i = 1; i <= n; i++) {
		if(fok[i] == 1) {
			sor[u] = i;
			u++;
			L[i] = i;
			kezd++;
		} else {
			L[i] = -1;
		}
		tovabb[i] = true;
	}

	while(e <= u && u != 0) {
		if(tovabb[sor[e]]) {
			for(auto i : szom[sor[e]]) {
				if(L[i] == -1) {
					sor[u] = i;
					u++;
					L[i] = L[sor[e]];
					if(fok[i] != 2) tovabb[i] = false; 
				} else if(L[i] != L[sor[e]] && fok[i] <= 2) {
					sor[u] = L[i];
					u++;
					sor[u] = L[sor[e]];
					u++;
					tovabb[i] = false;
					tovabb[sor[e]] = false;
				}
			}
		}
		e++;
	}

	cout << u-kezd << '\n';
	if(u-kezd > 1) msort(kezd, u-1);
	for(int i = kezd; i < u; i++) cout << sor[i] << ' ';

	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/028ms1332 KiB
3Elfogadva2/21ms508 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/21ms376 KiB
8Elfogadva2/23ms328 KiB
9Elfogadva2/24ms564 KiB
10Elfogadva2/28ms608 KiB
11Elfogadva2/214ms764 KiB
12Elfogadva2/214ms804 KiB
13Elfogadva3/32ms316 KiB
14Elfogadva3/34ms552 KiB
15Elfogadva3/34ms572 KiB
16Elfogadva3/34ms564 KiB
17Elfogadva3/312ms848 KiB
18Elfogadva3/314ms908 KiB
19Elfogadva3/317ms1108 KiB
20Elfogadva3/328ms1168 KiB
21Elfogadva3/328ms1252 KiB
22Elfogadva3/328ms1316 KiB