84742024-01-17 11:45:03GervidKerékpártúra (50 pont)cpp17Elfogadva 50/50200ms11484 KiB
#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int main()
{
	int n, m, start, i, node1, node2;
	cin >> n >> m >> start;
	start--;

	vector<vector<int>> normal(n), reversed(n);

	for (i = 0; i < m; i++)
	{
		cin >> node1 >> node2;
		
		normal[node1 - 1].push_back(node2 - 1);
		reversed[node2 - 1].push_back(node1 - 1);
	}

	set<int> canreturn, canreach;
	canreach.insert(start);
	canreturn.insert(start);
	
	queue<int> q;
	q.push(start);

	while (q.size() > 0)
	{
		for (i = 0; i < normal[q.front()].size(); i++)
		{
			if (!canreach.count(normal[q.front()][i]))
			{
				canreach.insert(normal[q.front()][i]);
				q.push(normal[q.front()][i]);
			}
		}
		q.pop();
	}

	q.push(start);

	while (q.size() > 0)
	{
		for (i = 0; i < reversed[q.front()].size(); i++)
		{
			if (!canreturn.count(reversed[q.front()][i]))
			{
				canreturn.insert(reversed[q.front()][i]);
				q.push(reversed[q.front()][i]);
			}
		}
		q.pop();
	}

	vector<int> creturn;

	for (auto element : canreach)
	{
		if (canreturn.count(element))
		{
			creturn.push_back(element);
		}
	}

	set<int> been;
	for (i = 0; i < creturn.size(); i++)
	{
		been.insert(creturn[i]);
	}

	for (i = 0; i < creturn.size(); i++)
	{
		for (int j = 0; j < normal[creturn[i]].size(); j++)
		{
			int neighbour = normal[creturn[i]][j];

			if (!been.count(neighbour))
			{
				been.insert(neighbour);
			}
		}
	}

	cout << been.size()-1 << endl;

	for (auto element : been)
	{
		if (element != start)
		{
			cout << element + 1 << ' ';
		}
	}
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1808 KiB
2Elfogadva0/026ms4912 KiB
3Elfogadva2/23ms2212 KiB
4Elfogadva2/23ms2304 KiB
5Elfogadva2/23ms2428 KiB
6Elfogadva2/23ms2652 KiB
7Elfogadva2/23ms2892 KiB
8Elfogadva2/24ms3116 KiB
9Elfogadva2/24ms3024 KiB
10Elfogadva2/24ms3320 KiB
11Elfogadva2/27ms3528 KiB
12Elfogadva2/214ms3756 KiB
13Elfogadva2/214ms3760 KiB
14Elfogadva2/227ms4268 KiB
15Elfogadva3/346ms7100 KiB
16Elfogadva4/452ms7780 KiB
17Elfogadva4/475ms8536 KiB
18Elfogadva3/368ms8276 KiB
19Elfogadva3/359ms8148 KiB
20Elfogadva3/3156ms9704 KiB
21Elfogadva3/3194ms10984 KiB
22Elfogadva3/3200ms11484 KiB