166602025-05-07 19:32:51sztomiFertőzési sorozat (50 pont)cpp17Hibás válasz 47/5013ms508 KiB
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> felosztas; // bad practice
vector<vector<int>> graf;
vector<int> volt;
vector<int> sor;
vector<int> kell;
int akt_volt = 1;

bool jo_felosztas(){
    int akt_max = felosztas[sor[0]];
    int db = 0;
    bool kezdo = true;
    for(int i = 0; i < sor.size(); i++){
        if(felosztas[sor[i]] < akt_max || felosztas[sor[i]]-akt_max > 1){
            return false;
        }
        // ugy valt, hogy meg nem vegzett minden elotte levovel
        if(felosztas[sor[i]]-akt_max == 1){
            if(kezdo){
                kezdo = false;
            }
            else{
                if(db != kell[felosztas[sor[i-1]]]){
                    return false;
                }
            }
            db = 0;
        }
        db++;


        akt_max = max(felosztas[sor[i]], akt_max);
    }
    return true;
}

void bfs(int kezd){
    kell.assign(n, 0);
    queue<int> q;
    q.push(kezd);
    volt[kezd] = akt_volt;
    felosztas[kezd] = 0;
    kell[0] = 1;
    int akt;
    while(!q.empty()){
        akt = q.front();
        //cout << "akt: " <<akt << " lepes: " << lepes << "\n";
        q.pop();

        for(auto x : graf[akt]){
            if(volt[x] == akt_volt){
                continue;
            }
            felosztas[x] = felosztas[akt] + 1;
            kell[felosztas[x]]++;
            volt[x] = akt_volt;
            q.push(x);
        }
    }

    int sz = 0;
    for(int i = 0; i < n; i++){
        if(kell[i] == 0) break;
        sz += kell[i];
        kell[i] = sz;
    }


    akt_volt++;
}


int main()
{
    int m, k;
    cin >> n >> m >> k;
    sor.resize(k);
    for(auto &x : sor){
        cin >> x;
        x--;
    }

    graf.assign(n, vector<int>());

    volt.assign(n, 0);
    int a, b;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        a--;
        b--;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }


    vector<int> jok;
    felosztas.assign(n, -1);
    for(int i = 0; i < n; i++){
        bfs(i);
        /*
        for(int j = 0; j < n; j++){
            cout << felosztas[j] << " ";
        }
        cout << "\n";
        */
        if(jo_felosztas()){
            //cout << "jo felosztas\n";
            jok.push_back(i+1);
        }
    }

    cout << jok.size() << "\n";
    for(auto x : jok){
        cout << x << " ";
    }
    cout << "\n";

}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base47/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/04ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/23ms424 KiB
7Elfogadva2/24ms416 KiB
8Elfogadva2/24ms316 KiB
9Elfogadva2/24ms428 KiB
10Elfogadva2/212ms440 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/24ms436 KiB
13Elfogadva2/27ms500 KiB
14Elfogadva2/24ms316 KiB
15Elfogadva2/24ms432 KiB
16Elfogadva2/26ms436 KiB
17Elfogadva2/24ms432 KiB
18Hibás válasz0/14ms432 KiB
19Elfogadva1/16ms316 KiB
20Elfogadva1/14ms436 KiB
21Elfogadva1/112ms436 KiB
22Elfogadva1/112ms440 KiB
23Hibás válasz0/110ms444 KiB
24Elfogadva1/19ms316 KiB
25Elfogadva1/18ms316 KiB
26Elfogadva1/110ms436 KiB
27Elfogadva1/112ms444 KiB
28Elfogadva1/110ms440 KiB
29Elfogadva1/112ms316 KiB
30Elfogadva1/19ms436 KiB
31Elfogadva1/19ms440 KiB
32Elfogadva1/110ms440 KiB
33Hibás válasz0/113ms440 KiB
34Elfogadva1/113ms508 KiB
35Elfogadva1/112ms508 KiB
36Elfogadva1/112ms440 KiB
37Elfogadva1/112ms440 KiB
38Elfogadva1/112ms436 KiB
39Elfogadva1/110ms428 KiB
40Elfogadva1/112ms432 KiB