201132026-01-01 21:58:25hunzombiFertőzési sorozat (50 pont)cpp17Elfogadva 50/5013ms616 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<int> ismert;
vector<vector<int>> graph;

bool valid(int root) {
    vector<int> dist(n + 1, -1), days_cnt;
    queue<int> q;
    dist[root] = 0;
    q.push(root);

    while (!q.empty()) {
        int sz = q.size();
        int cnt = 0;
        for (int i=0; i < sz; i++) {
            int node = q.front();
            q.pop();
            cnt++;
            for (int next : graph[node]) {
                if (dist[next] == -1) {
                    dist[next] = dist[node] + 1;
                    q.push(next);
                }
            }
        }
        days_cnt.push_back(cnt);
    }

    int start = INT_MAX;
    int finish = -1;

    for (int person : ismert) {
        days_cnt[dist[person]]--;
        start = min(start, dist[person]);
        finish = max(finish, dist[person]);
    }

    for (int i=1; i < ismert.size(); i++) {
        if (dist[ismert[i-1]] > dist[ismert[i]]) return false;
    }

    for (int i = start + 1; i < finish; i++) {
        if (days_cnt[i] > 0) return false;
    }

    return true;
}

int main() {
    cin >> n >> m >> k;
    ismert.assign(k, 0);
    graph.assign(n + 1, vector<int>());
    for (int i = 0; i < k; i++) {
        cin >> ismert[i];
    }
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> res;
    for (int i=1; i <= n; i++) {
        if (valid(i)) {
            res.push_back(i);
        }
    }

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

    cout << res.size() << '\n';
    for (int num : res) {
        cout << num << ' ';
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/02ms316 KiB
2Elfogadva0/02ms316 KiB
3Elfogadva0/04ms564 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/23ms316 KiB
7Elfogadva2/24ms316 KiB
8Elfogadva2/24ms316 KiB
9Elfogadva2/24ms348 KiB
10Elfogadva2/212ms440 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/24ms536 KiB
13Elfogadva2/26ms316 KiB
14Elfogadva2/24ms316 KiB
15Elfogadva2/24ms416 KiB
16Elfogadva2/26ms432 KiB
17Elfogadva2/24ms316 KiB
18Elfogadva1/14ms316 KiB
19Elfogadva1/16ms432 KiB
20Elfogadva1/14ms316 KiB
21Elfogadva1/112ms436 KiB
22Elfogadva1/112ms616 KiB
23Elfogadva1/110ms316 KiB
24Elfogadva1/110ms436 KiB
25Elfogadva1/18ms444 KiB
26Elfogadva1/110ms436 KiB
27Elfogadva1/112ms316 KiB
28Elfogadva1/110ms324 KiB
29Elfogadva1/112ms432 KiB
30Elfogadva1/19ms436 KiB
31Elfogadva1/19ms436 KiB
32Elfogadva1/110ms436 KiB
33Elfogadva1/113ms432 KiB
34Elfogadva1/112ms440 KiB
35Elfogadva1/112ms440 KiB
36Elfogadva1/112ms316 KiB
37Elfogadva1/112ms436 KiB
38Elfogadva1/112ms316 KiB
39Elfogadva1/110ms500 KiB
40Elfogadva1/113ms436 KiB