1595 | 2022. 11. 28 20:26:27 | kicsiboglar | Hálózati biztonság (50) | cpp11 | Elfogadva 50/50 | 171ms | 30948 KiB |
#include <iostream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;
ll i, j, n, m, k, a, b;
struct element
{
ll neighbor;
bool ok = true;
vector <ll> sz;
};
struct adat
{
ll id, nr;
};
adat p;
priority_queue <adat> que;
bool operator<(const adat& a, const adat& b)
{
return a.nr > b.nr;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
vector <element> x(n + 1);
for (i = 1; i <= m; ++i)
{
cin >> a >> b;
x[a].neighbor++;
x[b].neighbor++;
x[a].sz.push_back(b);
x[b].sz.push_back(a);
}
for (i = 1; i <= n; ++i)
{
p.id = i;
p.nr = x[i].neighbor;
que.push(p);
}
adat curr;
while (!que.empty())
{
curr = que.top();
while (!que.empty() && !x[curr.id].ok)
{
que.pop();
if (!que.empty()) curr = que.top();
}
if (que.empty()) break;
que.pop();
if (x[curr.id].neighbor >= k) break;
else
{
for (auto e : x[curr.id].sz)
{
x[e].neighbor--;
if (x[e].neighbor == 0) x[e].ok = false;
else
{
p.id = e;
p.nr = x[e].neighbor;
que.push({ e, x[e].neighbor });
}
}
x[curr.id].ok = false;
x[curr.id].neighbor = 0;
}
}
ll db = 0;
for (i = 1; i <= n; ++i) if (x[i].ok) db++;
cout << db << '\n';
for (i = 1; i <= n; ++i) if (x[i].ok) cout << i << " ";
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 82ms | 16108 KiB | |||
3 | Elfogadva | 2/2 | 2ms | 2228 KiB | |||
4 | Elfogadva | 2/2 | 2ms | 2308 KiB | |||
5 | Elfogadva | 2/2 | 2ms | 2444 KiB | |||
6 | Elfogadva | 2/2 | 2ms | 2644 KiB | |||
7 | Elfogadva | 2/2 | 2ms | 2724 KiB | |||
8 | Elfogadva | 2/2 | 2ms | 3096 KiB | |||
9 | Elfogadva | 2/2 | 2ms | 3288 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 4220 KiB | |||
11 | Elfogadva | 2/2 | 3ms | 4108 KiB | |||
12 | Elfogadva | 2/2 | 4ms | 4404 KiB | |||
13 | Elfogadva | 3/3 | 3ms | 4032 KiB | |||
14 | Elfogadva | 3/3 | 6ms | 5356 KiB | |||
15 | Elfogadva | 3/3 | 8ms | 6876 KiB | |||
16 | Elfogadva | 3/3 | 75ms | 15544 KiB | |||
17 | Elfogadva | 3/3 | 7ms | 4824 KiB | |||
18 | Elfogadva | 3/3 | 14ms | 10540 KiB | |||
19 | Elfogadva | 3/3 | 94ms | 22384 KiB | |||
20 | Elfogadva | 3/3 | 171ms | 30948 KiB | |||
21 | Elfogadva | 3/3 | 98ms | 23360 KiB | |||
22 | Elfogadva | 3/3 | 2ms | 3920 KiB |