146412025-01-23 16:16:21zsombHálózati biztonság (50)cpp17Accepted 50/50171ms11496 KiB
#include <bits/stdc++.h>
using namespace std;

struct node
{
    vector<int> order_;

    int in = 1;
    int connCount = 0;
};

void halfBFS(vector<node> *graph, int currIdx, int k) //, vector<int> *queue
{
    if ((*graph)[currIdx].connCount < k && (*graph)[currIdx].in != 0)
    {
        (*graph)[currIdx].in = 0;

        for (int i = 0; i < (*graph)[currIdx].order_.size(); i++)
        {
            int nextIdx = (*graph)[currIdx].order_[i];

            (*graph)[currIdx].connCount = 0;
            (*graph)[nextIdx].connCount--;
            if ((*graph)[nextIdx].connCount < k && (*graph)[nextIdx].in != 0)
            {
                halfBFS(graph, nextIdx, k);
            }
        }
    }
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<node> graph(n + 1);
    graph[0].in = 0;
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;

        graph[u].order_.push_back(v);
        graph[v].order_.push_back(u);

        graph[u].connCount++;
        graph[v].connCount++;
    }
    vector<int> q(0);

    for (int i = 1; i < n + 1; i++)
    {
        if (graph[i].connCount < k)
            halfBFS(&graph, i, k);
    }

    int ossz = 0;
    vector<int> end(0);
    for (int i = 1; i < n + 1; i++)
    {
        if (graph[i].in == 1)
        {
            ossz++;
            end.push_back(i);
        }
    }
    cout << ossz << endl;

    for (int i = 0; i < end.size(); i++)
    {
        cout << end[i] << " ";
    }
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms508 KiB
2Accepted0/0104ms6024 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/21ms316 KiB
8Accepted2/21ms316 KiB
9Accepted2/21ms316 KiB
10Accepted2/26ms564 KiB
11Accepted2/22ms316 KiB
12Accepted2/24ms524 KiB
13Accepted3/31ms316 KiB
14Accepted3/36ms820 KiB
15Accepted3/37ms1132 KiB
16Accepted3/382ms4744 KiB
17Accepted3/36ms824 KiB
18Accepted3/312ms2244 KiB
19Accepted3/3103ms8204 KiB
20Accepted3/3171ms11496 KiB
21Accepted3/3127ms8504 KiB
22Accepted3/31ms504 KiB