154122025-02-19 12:37:40ZsBalazsFertőzési sorozat (50 pont)cpp17Hibás válasz 34/5014ms608 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, k;

vector<vector<int>> graph;
vector<int> elemek;
vector<int> sorozat;

bool eset(int indulas) {
    elemek.assign(n, 0);
    
    queue<pair<int, int>> sor;
    sor.push({indulas, 1});
    
    while(!sor.empty()) {
        int current = sor.front().first;
        int napocska = sor.front().second;
        sor.pop();
        
        if (elemek[current] != 0) continue;
        
        elemek[current] = napocska;
        
        for (int szom : graph[current]) {
            sor.push({szom, napocska+1});
        }
    }
    
    // Check if this is valid?
    bool okes = true;
    int most = elemek[sorozat[0]];
    
    for (int i = 0; k > i && okes; i++) {
        int jelenleg = elemek[sorozat[i]];
        
        if (jelenleg != most) {
            if (jelenleg < most) {
                okes = false;
            } else if (jelenleg - most != 1) {
                okes = false;
            }
        }
    }
    
    return okes;
}

int main() {
	cin >> n >> m >> k;
	
    for (int i = 0; k > i; i++) {
        int temp;
        cin >> temp;
        
        temp--;
        
        sorozat.push_back(temp);
    }
    
    graph.resize(n);
    
    for (int i = 0; m > i; i++) {
        int a, b;
        cin >> a >> b;
        
        a--;
        b--;
        
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    vector<int> megoldasok;
    
    for (int i = 0; n > i; i++) {
        // Vegigprobaljuk az eseteket!!
        
        if (eset(i)) {
            megoldasok.push_back(i);
        }
    }
    
    cout << megoldasok.size() << endl;
    for (int kiki : megoldasok) {
        cout << kiki+1 << " ";
    }
    cout << endl;
    
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base34/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/04ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/24ms608 KiB
7Elfogadva2/24ms420 KiB
8Elfogadva2/24ms420 KiB
9Elfogadva2/24ms428 KiB
10Elfogadva2/214ms440 KiB
11Elfogadva1/12ms440 KiB
12Elfogadva2/28ms508 KiB
13Elfogadva2/28ms508 KiB
14Elfogadva2/27ms316 KiB
15Elfogadva2/28ms428 KiB
16Elfogadva2/28ms316 KiB
17Elfogadva2/26ms508 KiB
18Hibás válasz0/18ms432 KiB
19Elfogadva1/18ms316 KiB
20Elfogadva1/16ms316 KiB
21Elfogadva1/114ms440 KiB
22Elfogadva1/114ms440 KiB
23Hibás válasz0/114ms436 KiB
24Hibás válasz0/113ms316 KiB
25Hibás válasz0/113ms452 KiB
26Hibás válasz0/114ms316 KiB
27Hibás válasz0/114ms316 KiB
28Hibás válasz0/114ms436 KiB
29Elfogadva1/114ms436 KiB
30Hibás válasz0/113ms316 KiB
31Hibás válasz0/114ms444 KiB
32Hibás válasz0/114ms316 KiB
33Hibás válasz0/114ms508 KiB
34Hibás válasz0/114ms444 KiB
35Hibás válasz0/114ms316 KiB
36Hibás válasz0/114ms444 KiB
37Hibás válasz0/114ms316 KiB
38Hibás válasz0/114ms436 KiB
39Elfogadva1/114ms500 KiB
40Elfogadva1/114ms500 KiB