152952025-02-18 09:06:04AblablablaFertőzési sorozat (50 pont)cpp17Elfogadva 50/5019ms596 KiB
#include <bits/stdc++.h>

using namespace std;

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

    vector<int> alap(k);
    for(int &x : alap){
        cin >> x;
        x--;
    }

    vector<vector<int>> csucsok(n, vector<int>());
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;

        csucsok[a].push_back(b);
        csucsok[b].push_back(a);
    }

    vector<int> ans;

    for(int kezd = 0; kezd < n; kezd++){
        vector<bool> bejart(n);
        vector<int> tav(n, 2e9 + 7);
        int maxi = 0;
        queue<int> bejar;
        bejar.push(kezd);
        tav[kezd] = 0;

        while(!bejar.empty()){
            int akt = bejar.front();
            maxi = max(maxi, tav[akt]);
            bejar.pop();

            if(bejart[akt]) continue;

            bejart[akt] = 1;

            for(int x : csucsok[akt]){
                if(bejart[x]) continue;

                tav[x] = min(tav[x], tav[akt] + 1);
                bejar.push(x);
            }
        }

        vector<int> db(maxi + 1);
        for(int x : tav){
            db[x]++;
        }

        bool jo = 1;
        int elozo = tav[alap[0]];
        bool elso = 1;
        db[elozo]--;
        for(int i = 1; i < k; i++){
            int akt = tav[alap[i]];

            if(elozo != akt){
                if(akt < elozo || akt - elozo >= 2 || (!elso && db[elozo] != 0)){
                    jo = 0;
                    break;
                }
                elso = 0;
                elozo = akt;
            }

            db[akt]--;
        }

        if(jo){
            ans.push_back(kezd + 1);
        }
    }

    cout << ans.size() << "\n";
    for(int x : ans){
        cout << x << " ";
    }
    cout << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms500 KiB
3Elfogadva0/06ms316 KiB
4Elfogadva2/21ms500 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/24ms316 KiB
7Elfogadva2/24ms316 KiB
8Elfogadva2/24ms320 KiB
9Elfogadva2/27ms424 KiB
10Elfogadva2/219ms436 KiB
11Elfogadva1/12ms316 KiB
12Elfogadva2/27ms440 KiB
13Elfogadva2/27ms316 KiB
14Elfogadva2/26ms436 KiB
15Elfogadva2/27ms436 KiB
16Elfogadva2/28ms432 KiB
17Elfogadva2/26ms432 KiB
18Elfogadva1/17ms420 KiB
19Elfogadva1/17ms432 KiB
20Elfogadva1/16ms440 KiB
21Elfogadva1/119ms500 KiB
22Elfogadva1/119ms376 KiB
23Elfogadva1/117ms432 KiB
24Elfogadva1/117ms436 KiB
25Elfogadva1/116ms440 KiB
26Elfogadva1/117ms432 KiB
27Elfogadva1/119ms436 KiB
28Elfogadva1/117ms432 KiB
29Elfogadva1/118ms432 KiB
30Elfogadva1/117ms436 KiB
31Elfogadva1/117ms436 KiB
32Elfogadva1/117ms436 KiB
33Elfogadva1/119ms316 KiB
34Elfogadva1/119ms436 KiB
35Elfogadva1/119ms432 KiB
36Elfogadva1/119ms316 KiB
37Elfogadva1/119ms596 KiB
38Elfogadva1/119ms436 KiB
39Elfogadva1/117ms436 KiB
40Elfogadva1/119ms436 KiB