82122024-01-12 19:48:35CsongiElágazás nélküli úton levő települések (50 pont)cpp17Wrong answer 4/5029ms5564 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 << " ";
		}
	}
}
SubtaskSumTestVerdictTimeMemory
base4/50
1Accepted0/03ms1816 KiB
2Wrong answer0/028ms3916 KiB
3Wrong answer0/23ms2264 KiB
4Wrong answer0/23ms2428 KiB
5Accepted2/23ms2668 KiB
6Wrong answer0/23ms2924 KiB
7Accepted2/23ms3032 KiB
8Wrong answer0/24ms3044 KiB
9Wrong answer0/26ms3480 KiB
10Wrong answer0/28ms3796 KiB
11Wrong answer0/214ms4184 KiB
12Wrong answer0/216ms4508 KiB
13Wrong answer0/34ms3552 KiB
14Wrong answer0/36ms3804 KiB
15Wrong answer0/36ms3820 KiB
16Wrong answer0/38ms4096 KiB
17Wrong answer0/314ms4368 KiB
18Wrong answer0/314ms4384 KiB
19Wrong answer0/317ms4832 KiB
20Wrong answer0/328ms4996 KiB
21Wrong answer0/328ms5564 KiB
22Wrong answer0/329ms5524 KiB