145832025-01-19 14:18:56zsombHálózati biztonság (50)cpp17Időlimit túllépés 31/50400ms32000 KiB
#include <bits/stdc++.h>
using namespace std;

struct node
{
    vector<int> order_;
    unordered_map<int, int> to;
    int in = 1;
    int connCount = 0;
};

void halfBFS(vector<node> *graph, int currIdx, vector<int> *queue, int k)
{
    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];

            (*queue).push_back(nextIdx);

            (*graph)[currIdx].to[nextIdx] = 0;
            (*graph)[nextIdx].to[currIdx] = 0;
            (*graph)[currIdx].connCount = 0;
            (*graph)[nextIdx].connCount--;
        }

        while ((*queue).size() != 0)
        {
            int d = (*queue)[0];
            (*queue).erase((*queue).begin());
            halfBFS(graph, d, queue, 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].to[v] = 1;
        graph[v].to[u] = 1;

        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; i++)
    {
        if (graph[i].connCount < k)
            halfBFS(&graph, i, &q, k);
    }

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

    // sort(end.begin(), end.end());

    for (int i = 0; i < end.size(); i++)
    {
        cout << end[i] << " ";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base31/50
1Elfogadva0/01ms508 KiB
2Időlimit túllépés0/0384ms20912 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Hibás válasz0/21ms316 KiB
6Elfogadva2/21ms556 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/22ms316 KiB
9Elfogadva2/21ms316 KiB
10Hibás válasz0/210ms1332 KiB
11Elfogadva2/22ms564 KiB
12Elfogadva2/27ms1416 KiB
13Elfogadva3/32ms820 KiB
14Elfogadva3/39ms2428 KiB
15Elfogadva3/314ms3764 KiB
16Időlimit túllépés0/3400ms16660 KiB
17Elfogadva3/314ms2840 KiB
18Elfogadva3/323ms6548 KiB
19Időlimit túllépés0/3391ms32000 KiB
20Futási hiba0/3233ms32000 KiB
21Időlimit túllépés0/3324ms32000 KiB
22Hibás válasz0/31ms316 KiB