159022025-03-09 10:16:46NagyMartonFertőzési sorozat (50 pont)cpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base42/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/07ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/26ms420 KiB
7Elfogadva2/26ms416 KiB
8Elfogadva2/26ms316 KiB
9Elfogadva2/28ms428 KiB
10Elfogadva2/223ms388 KiB
11Elfogadva1/12ms316 KiB
12Elfogadva2/213ms508 KiB
13Elfogadva2/213ms436 KiB
14Elfogadva2/29ms444 KiB
15Elfogadva2/212ms356 KiB
16Elfogadva2/213ms428 KiB
17Elfogadva2/29ms316 KiB
18Elfogadva1/113ms316 KiB
19Elfogadva1/112ms316 KiB
20Elfogadva1/19ms316 KiB
21Elfogadva1/123ms632 KiB
22Elfogadva1/121ms432 KiB
23Elfogadva1/121ms440 KiB
24Hibás válasz0/120ms440 KiB
25Elfogadva1/120ms316 KiB
26Elfogadva1/121ms516 KiB
27Hibás válasz0/123ms316 KiB
28Hibás válasz0/121ms440 KiB
29Elfogadva1/121ms512 KiB
30Hibás válasz0/120ms316 KiB
31Hibás válasz0/120ms316 KiB
32Elfogadva1/121ms448 KiB
33Elfogadva1/123ms444 KiB
34Hibás válasz0/123ms448 KiB
35Hibás válasz0/123ms444 KiB
36Hibás válasz0/123ms444 KiB
37Elfogadva1/123ms316 KiB
38Elfogadva1/123ms316 KiB
39Elfogadva1/121ms316 KiB
40Elfogadva1/123ms508 KiB