238402026-01-30 16:59:10Rokus23Fertőzési sorozat (50 pont)cpp17Accepted 50/5013ms536 KiB
#include <bits/stdc++.h>
#include <queue>
using namespace std;
using ll = long long;
using pii = pair<int,int>;

bool init(vector<int>& v, int N) {
	for(int i=0;i<v.size();i++) {
		if(v[i]==N) return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
	int N,M,K;cin>>N>>M>>K;
	vector<vector<int>> g(N);
	vector<int> sorozat(K);
	for(int i=0;i<K;i++) cin>>sorozat[i];
	for(int i=0;i<K;i++) sorozat[i]--;
	for(int i=0;i<M;i++) {
		int a,b;
		cin>>a>>b;
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}
	vector<int> ans;
	for(int i=0;i<N;i++) {
		queue<int> q;
		vector<int> dist(N,-1);
		dist[i]=0;
		q.push(i);
		while(!q.empty()) {
			int v=q.front();
			q.pop();
			for(int u:g[v]) {
				if(dist[u]==-1) {
					dist[u]=dist[v]+1;
					q.push(u);
				}
			}
		}
		bool b=true;
		for(int j=0;j<K-1;j++) if(dist[sorozat[j]]>dist[sorozat[j+1]]) b=false;
		if(b) {
			int min1=dist[sorozat[0]],max1=dist[sorozat[K-1]];
			for(int j=0;j<N;j++) if(!init(sorozat,j) && dist[j]<max1 && dist[j]>min1) b=false;
		}
		if(b) ans.push_back(i+1);
	}
	cout<<ans.size()<<"\n";
	for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/01ms500 KiB
2Accepted0/01ms316 KiB
3Accepted0/04ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/24ms316 KiB
7Accepted2/24ms316 KiB
8Accepted2/24ms316 KiB
9Accepted2/24ms536 KiB
10Accepted2/213ms460 KiB
11Accepted1/11ms316 KiB
12Accepted2/27ms316 KiB
13Accepted2/28ms316 KiB
14Accepted2/26ms316 KiB
15Accepted2/28ms536 KiB
16Accepted2/27ms456 KiB
17Accepted2/24ms324 KiB
18Accepted1/14ms332 KiB
19Accepted1/16ms452 KiB
20Accepted1/17ms456 KiB
21Accepted1/110ms444 KiB
22Accepted1/110ms460 KiB
23Accepted1/19ms452 KiB
24Accepted1/19ms460 KiB
25Accepted1/112ms464 KiB
26Accepted1/110ms464 KiB
27Accepted1/112ms456 KiB
28Accepted1/19ms316 KiB
29Accepted1/110ms316 KiB
30Accepted1/112ms316 KiB
31Accepted1/19ms316 KiB
32Accepted1/19ms460 KiB
33Accepted1/112ms452 KiB
34Accepted1/112ms464 KiB
35Accepted1/113ms508 KiB
36Accepted1/112ms460 KiB
37Accepted1/110ms456 KiB
38Accepted1/112ms500 KiB
39Accepted1/19ms316 KiB
40Accepted1/110ms316 KiB