156042025-02-21 08:07:59ZsBalazsFertőzési sorozat (50 pont)cpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/06ms424 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/24ms316 KiB
7Elfogadva2/24ms416 KiB
8Elfogadva2/24ms500 KiB
9Elfogadva2/27ms424 KiB
10Elfogadva2/218ms444 KiB
11Elfogadva1/12ms316 KiB
12Elfogadva2/28ms432 KiB
13Elfogadva2/28ms436 KiB
14Elfogadva2/28ms436 KiB
15Elfogadva2/28ms316 KiB
16Elfogadva2/29ms508 KiB
17Elfogadva2/28ms316 KiB
18Elfogadva1/19ms316 KiB
19Elfogadva1/18ms436 KiB
20Elfogadva1/18ms368 KiB
21Elfogadva1/118ms448 KiB
22Elfogadva1/117ms440 KiB
23Elfogadva1/117ms444 KiB
24Elfogadva1/117ms416 KiB
25Elfogadva1/117ms500 KiB
26Elfogadva1/117ms328 KiB
27Elfogadva1/118ms440 KiB
28Elfogadva1/117ms436 KiB
29Elfogadva1/118ms316 KiB
30Elfogadva1/117ms332 KiB
31Elfogadva1/117ms508 KiB
32Elfogadva1/117ms444 KiB
33Elfogadva1/118ms508 KiB
34Elfogadva1/118ms500 KiB
35Elfogadva1/118ms444 KiB
36Elfogadva1/118ms444 KiB
37Elfogadva1/118ms508 KiB
38Elfogadva1/118ms508 KiB
39Elfogadva1/117ms316 KiB
40Elfogadva1/118ms508 KiB