8212 2024. 01. 12 19:48:35 Csongi Elágazás nélküli úton levő települések (50 pont) cpp17 Hibás válasz 4/50 29ms 5564 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <unordered_set>
#include <queue>
#include <string>
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n+1);
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	unordered_set<int> zsakok;
	for (int i = 0; i < adj.size(); i++)
	{
		if (adj[i].size() == 1)
			zsakok.insert(i);
	}
	vector<int> zsakfalu(zsakok.begin(), zsakok.end());
	int megnezve = 0;
	queue<int> sor;
	vector<int> megold(0);
	for (int i = 0; i < zsakfalu.size(); i++)
	{
		sor.push(zsakfalu[i]);
		vector<bool> check(n + 1);
		vector<int> path(0);
		path.push_back(zsakfalu[i]);
		bool vege = false;
		while (sor.size() != 0)
		{
			int most = sor.front();
			sor.pop();
			//cout << most << " ";
			for (int x : adj[most])
			{
				if (!check[x] && x != most && !vege && adj[x].size() < 3)
				{
					sor.push(x);
					path.push_back(x);
					check[x] = true;
					check[most] = true;
				}
				else if (!check[x] && adj[x].size() <= 3 && !vege)
				{
					sor.push(x);
					path.push_back(x);
					check[x] = true;
					check[most] = true;
					vege = true;
					break;
				}
			}
			megnezve++;
		}
		for (int x : path)
		{
			megold.push_back(x);
		}
	}
	cout << megold.size() - zsakfalu.size() << endl;
	sort(megold.begin(), megold.end());
	for (int y : megold)
	{
		if (find(zsakfalu.begin(), zsakfalu.end(), y) == zsakfalu.end())
		{
			cout << y << " ";
		}
	}
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 4/50
1 Elfogadva 0/0 3ms 1816 KiB
2 Hibás válasz 0/0 28ms 3916 KiB
3 Hibás válasz 0/2 3ms 2264 KiB
4 Hibás válasz 0/2 3ms 2428 KiB
5 Elfogadva 2/2 3ms 2668 KiB
6 Hibás válasz 0/2 3ms 2924 KiB
7 Elfogadva 2/2 3ms 3032 KiB
8 Hibás válasz 0/2 4ms 3044 KiB
9 Hibás válasz 0/2 6ms 3480 KiB
10 Hibás válasz 0/2 8ms 3796 KiB
11 Hibás válasz 0/2 14ms 4184 KiB
12 Hibás válasz 0/2 16ms 4508 KiB
13 Hibás válasz 0/3 4ms 3552 KiB
14 Hibás válasz 0/3 6ms 3804 KiB
15 Hibás válasz 0/3 6ms 3820 KiB
16 Hibás válasz 0/3 8ms 4096 KiB
17 Hibás válasz 0/3 14ms 4368 KiB
18 Hibás válasz 0/3 14ms 4384 KiB
19 Hibás válasz 0/3 17ms 4832 KiB
20 Hibás válasz 0/3 28ms 4996 KiB
21 Hibás válasz 0/3 28ms 5564 KiB
22 Hibás válasz 0/3 29ms 5524 KiB