159022025-03-09 10:16:46NagyMartonFertőzési sorozat (50 pont)cpp17Wrong answer 42/5023ms632 KiB
#include <bits/stdc++.h>
using namespace std;

vector <int> t;
vector <vector <int>> g;
vector <bool> b;
queue <pair <int, int>> q;

void vfs(int n, int d) {
    if (b[n] == false) {
        b[n] = true;
        t[n] = d;

        for (int i = 0; i < g[n].size(); i++) {
            q.push(pair <int, int> (g[n][i], d+1));
        }
    }

    q.pop();
    if (!q.empty()) {
        vfs(q.front().first, q.front().second);
    }
}

int main() {
	int n, m, k, c = 0;
    cin >> n >> m >> k;
    vector <int> a (k, 0);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
        a[i]--;
    }
    g.resize(n, vector <int> (0));
    for (int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        t1--;
        t2--;

        g[t1].push_back(t2);
        g[t2].push_back(t1);
    }
    b.resize(n, false);
    t.resize(n);
    vector <int> o (0);
	
    for (int i = 0; i < n; i++) {
        for (int i = 0; i < n; i++) {
            b[i] = false;
        }

        q.push(pair <int, int> (i, 0));
        vfs(i, 0);

        bool f = true;
        for (int j = 0; j < k-1; j++) {
            if (!((t[a[j]] == t[a[j+1]]) || (t[a[j]] == t[a[j+1]]-1))) {
                f = false;
                break;
            }
        }
        if (f) {
            o.push_back(i);
            c++;
        }
    }

    cout << c << endl;
    for (int i = 0; i < c; i++) {
        cout << o[i]+1 << ' ';
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base42/50
1Accepted0/01ms316 KiB
2Accepted0/01ms316 KiB
3Accepted0/07ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/22ms316 KiB
6Accepted2/26ms420 KiB
7Accepted2/26ms416 KiB
8Accepted2/26ms316 KiB
9Accepted2/28ms428 KiB
10Accepted2/223ms388 KiB
11Accepted1/12ms316 KiB
12Accepted2/213ms508 KiB
13Accepted2/213ms436 KiB
14Accepted2/29ms444 KiB
15Accepted2/212ms356 KiB
16Accepted2/213ms428 KiB
17Accepted2/29ms316 KiB
18Accepted1/113ms316 KiB
19Accepted1/112ms316 KiB
20Accepted1/19ms316 KiB
21Accepted1/123ms632 KiB
22Accepted1/121ms432 KiB
23Accepted1/121ms440 KiB
24Wrong answer0/120ms440 KiB
25Accepted1/120ms316 KiB
26Accepted1/121ms516 KiB
27Wrong answer0/123ms316 KiB
28Wrong answer0/121ms440 KiB
29Accepted1/121ms512 KiB
30Wrong answer0/120ms316 KiB
31Wrong answer0/120ms316 KiB
32Accepted1/121ms448 KiB
33Accepted1/123ms444 KiB
34Wrong answer0/123ms448 KiB
35Wrong answer0/123ms444 KiB
36Wrong answer0/123ms444 KiB
37Accepted1/123ms316 KiB
38Accepted1/123ms316 KiB
39Accepted1/121ms316 KiB
40Accepted1/123ms508 KiB