1352021-01-26 17:44:01kidesoHálózati biztonság (50)cpp11Elfogadva 50/50188ms25572 KiB
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

//ifstream cin("hali.in");
//ofstream cout("hali.out");

struct par
{
	int id, sz;
};

struct pont
{
	bool van = true;
	int sz = 0;
	vector <int> el;
};

priority_queue <par> p;
vector <pont> x;
vector <int> megold;
int N, M, K, i, a, b, dbm;
par akt;

bool operator < (const par& a, const par& b)
{
	return a.sz > b.sz;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> N >> M >> K;
	x.resize(N + 1);

	for (i = 1; i <= M; ++i)
	{
		cin >> a >> b;
		x[a].el.push_back(b);
		x[b].el.push_back(a);
		++x[a].sz;
		++x[b].sz;
	}

	for (i = 1; i <= N; ++i)
		p.push({ i,x[i].sz });

	dbm = N;
	while (p.top().sz < K)
	{
		akt = p.top();
		p.pop();
		if (x[akt.id].van)
		{
			x[akt.id].van = false;
			--dbm;
			for (int e : x[akt.id].el)
			{
				--x[e].sz;
				if (x[e].sz > 0) p.push({ e,x[e].sz });
			}
		}
	}

	cout << dbm << '\n';
	for (i = 1; i <= N; ++i)
		if (x[i].van) cout << i << ' ';
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/02ms1820 KiB
2Elfogadva0/090ms12176 KiB
3Elfogadva2/21ms3080 KiB
4Elfogadva2/21ms3052 KiB
5Elfogadva2/21ms3088 KiB
6Elfogadva2/21ms3080 KiB
7Elfogadva2/21ms3096 KiB
8Elfogadva2/21ms3116 KiB
9Elfogadva2/21ms3124 KiB
10Elfogadva2/24ms3572 KiB
11Elfogadva2/22ms3440 KiB
12Elfogadva2/23ms3772 KiB
13Elfogadva3/31ms3556 KiB
14Elfogadva3/34ms4656 KiB
15Elfogadva3/37ms5852 KiB
16Elfogadva3/378ms11852 KiB
17Elfogadva3/36ms5304 KiB
18Elfogadva3/312ms9612 KiB
19Elfogadva3/3108ms19736 KiB
20Elfogadva3/3188ms25572 KiB
21Elfogadva3/3104ms23396 KiB
22Elfogadva3/31ms9212 KiB