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