156042025-02-21 08:07:59ZsBalazsFertőzési sorozat (50 pont)cpp17Accepted 50/5018ms508 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
vector<int> sorozat;
vector<vector<int>> graph;

vector<int> napok;

bool test(int honnan) {
    napok.assign(n, 0);
    
    queue<pair<int, int>> sor;
    sor.push({honnan, 1});
    
    while (!sor.empty()) {
        int current = sor.front().first;
        int nap = sor.front().second;
        sor.pop();
        
        if (napok[current] != 0) continue;
        
        napok[current] = nap;
        
        for (int szom : graph[current]) {
            sor.push({szom, nap+1});
        }
    }
    
    bool good = true;
    
    vector<int> kik;
    
    int last = napok[sorozat[0]];
    for (int index : sorozat) {
        if (last != napok[index]) {
            kik.push_back(napok[index]);
            if (last+1 != napok[index]) {
                good = false;
                break;
            }
        }
        last = napok[index];
    }
    
    if (kik.size() > 0) kik.pop_back(); // Nem kell az utolsot nezni
    
    for (int ellenor : kik) {
        for (int i = 0; n > i && good; i++) {
            if (napok[i] == ellenor) {
                // Benne kell, hogy legyek a sorozatba!
                bool benne = false;
                
                for (int elem : sorozat) {
                    if (elem == i) {
                        benne = true;
                        break;
                    }
                }
                
                if (!benne) {
                    good = false;
                }
            }
        }
    }
    
    return good;
}

int main() {
	cin >> n >> m >> k;
	
	graph.resize(n);
	
	for (int i = 0; k > i; i++) {
	    int temp;
	    cin >> temp;
	    
	    sorozat.push_back(temp-1);
	}
	
	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++) {
	    if (test(i)) megoldasok.push_back(i);
	}
	
	cout << megoldasok.size() << endl;
	for (int megold : megoldasok) {
	    cout << megold+1 << " ";
	}
	cout << endl;
    
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms316 KiB
2Accepted0/01ms316 KiB
3Accepted0/06ms424 KiB
4Accepted2/21ms316 KiB
5Accepted2/22ms316 KiB
6Accepted2/24ms316 KiB
7Accepted2/24ms416 KiB
8Accepted2/24ms500 KiB
9Accepted2/27ms424 KiB
10Accepted2/218ms444 KiB
11Accepted1/12ms316 KiB
12Accepted2/28ms432 KiB
13Accepted2/28ms436 KiB
14Accepted2/28ms436 KiB
15Accepted2/28ms316 KiB
16Accepted2/29ms508 KiB
17Accepted2/28ms316 KiB
18Accepted1/19ms316 KiB
19Accepted1/18ms436 KiB
20Accepted1/18ms368 KiB
21Accepted1/118ms448 KiB
22Accepted1/117ms440 KiB
23Accepted1/117ms444 KiB
24Accepted1/117ms416 KiB
25Accepted1/117ms500 KiB
26Accepted1/117ms328 KiB
27Accepted1/118ms440 KiB
28Accepted1/117ms436 KiB
29Accepted1/118ms316 KiB
30Accepted1/117ms332 KiB
31Accepted1/117ms508 KiB
32Accepted1/117ms444 KiB
33Accepted1/118ms508 KiB
34Accepted1/118ms500 KiB
35Accepted1/118ms444 KiB
36Accepted1/118ms444 KiB
37Accepted1/118ms508 KiB
38Accepted1/118ms508 KiB
39Accepted1/117ms316 KiB
40Accepted1/118ms508 KiB