238402026-01-30 16:59:10Rokus23Fertőzési sorozat (50 pont)cpp17Elfogadva 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]<<" ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms500 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/04ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/24ms316 KiB
7Elfogadva2/24ms316 KiB
8Elfogadva2/24ms316 KiB
9Elfogadva2/24ms536 KiB
10Elfogadva2/213ms460 KiB
11Elfogadva1/11ms316 KiB
12Elfogadva2/27ms316 KiB
13Elfogadva2/28ms316 KiB
14Elfogadva2/26ms316 KiB
15Elfogadva2/28ms536 KiB
16Elfogadva2/27ms456 KiB
17Elfogadva2/24ms324 KiB
18Elfogadva1/14ms332 KiB
19Elfogadva1/16ms452 KiB
20Elfogadva1/17ms456 KiB
21Elfogadva1/110ms444 KiB
22Elfogadva1/110ms460 KiB
23Elfogadva1/19ms452 KiB
24Elfogadva1/19ms460 KiB
25Elfogadva1/112ms464 KiB
26Elfogadva1/110ms464 KiB
27Elfogadva1/112ms456 KiB
28Elfogadva1/19ms316 KiB
29Elfogadva1/110ms316 KiB
30Elfogadva1/112ms316 KiB
31Elfogadva1/19ms316 KiB
32Elfogadva1/19ms460 KiB
33Elfogadva1/112ms452 KiB
34Elfogadva1/112ms464 KiB
35Elfogadva1/113ms508 KiB
36Elfogadva1/112ms460 KiB
37Elfogadva1/110ms456 KiB
38Elfogadva1/112ms500 KiB
39Elfogadva1/19ms316 KiB
40Elfogadva1/110ms316 KiB