15952022-11-28 20:26:27kicsiboglarHálózati biztonság (50)cpp11Accepted 50/50171ms30948 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1828 KiB
2Accepted0/082ms16108 KiB
3Accepted2/22ms2228 KiB
4Accepted2/22ms2308 KiB
5Accepted2/22ms2444 KiB
6Accepted2/22ms2644 KiB
7Accepted2/22ms2724 KiB
8Accepted2/22ms3096 KiB
9Accepted2/22ms3288 KiB
10Accepted2/24ms4220 KiB
11Accepted2/23ms4108 KiB
12Accepted2/24ms4404 KiB
13Accepted3/33ms4032 KiB
14Accepted3/36ms5356 KiB
15Accepted3/38ms6876 KiB
16Accepted3/375ms15544 KiB
17Accepted3/37ms4824 KiB
18Accepted3/314ms10540 KiB
19Accepted3/394ms22384 KiB
20Accepted3/3171ms30948 KiB
21Accepted3/398ms23360 KiB
22Accepted3/32ms3920 KiB