156212025-02-21 10:34:02MatematikaFertőzési sorozat (50 pont)cpp17Elfogadva 50/5013ms540 KiB
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> vec;
vector<bool> kas;
vector<int> erdos,ki;

void bfs(queue<int>& q)
{
    int x=q.front();
    q.pop();
    for(auto& z:vec[x])
    {
        if(erdos[z]==0)
        {
            erdos[z]=erdos[x]+1;
            q.push(z);
        }
    }
    if(!q.empty())
        bfs(q);
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int n,m,k; cin >> n >> m >> k;
    vec.resize(n);
    kas.resize(n);
    erdos.resize(n);
    vector<int> be(k);
    for(auto& z:be)
    {
        cin >> z;
        z--;
        kas[z]=true;
    }
    for(int i=0; i<m; i++)
    {
        int a,b; cin >> a >> b;
        vec[a-1].push_back(b-1);
        vec[b-1].push_back(a-1);
    }
    for(int i=0; i<n; i++)
    {
        if(kas[i] && i!=be[0])
            continue;
        erdos.assign(n,0);
        erdos[i]=1;
        queue<int> q;
        q.push(i);
        bfs(q);
        /*for(auto z:erdos)
            cerr << z << " ";*/
        /*if(i==3)
            for(auto z:erdos)
                cerr << z << " ";*/
        bool berak=true;
        int elozo=be[0];
        for(auto& z:be)
        {
            if(erdos[z]!=erdos[elozo] && erdos[elozo]+1!=erdos[z])
            {
                berak=false;
                break;
            }
            elozo=z;
        }
        for(int j=0; j<n; j++)
            if(!kas[j] && (erdos[j]>erdos[be[0]] && erdos[j]<erdos[be.back()]))
                berak=false;
        if(berak)
            ki.push_back(i);
    }
    cout << ki.size() << "\n";
    for(auto& z:ki)
        cout << z+1 << " ";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms500 KiB
3Elfogadva0/04ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva2/24ms508 KiB
7Elfogadva2/24ms316 KiB
8Elfogadva2/24ms316 KiB
9Elfogadva2/24ms444 KiB
10Elfogadva2/212ms456 KiB
11Elfogadva1/11ms380 KiB
12Elfogadva2/24ms452 KiB
13Elfogadva2/26ms316 KiB
14Elfogadva2/24ms396 KiB
15Elfogadva2/26ms316 KiB
16Elfogadva2/26ms500 KiB
17Elfogadva2/24ms440 KiB
18Elfogadva1/14ms500 KiB
19Elfogadva1/16ms468 KiB
20Elfogadva1/14ms456 KiB
21Elfogadva1/112ms460 KiB
22Elfogadva1/112ms456 KiB
23Elfogadva1/19ms316 KiB
24Elfogadva1/19ms528 KiB
25Elfogadva1/18ms320 KiB
26Elfogadva1/19ms316 KiB
27Elfogadva1/112ms316 KiB
28Elfogadva1/110ms464 KiB
29Elfogadva1/112ms316 KiB
30Elfogadva1/19ms320 KiB
31Elfogadva1/19ms316 KiB
32Elfogadva1/110ms540 KiB
33Elfogadva1/11ms320 KiB
34Elfogadva1/112ms460 KiB
35Elfogadva1/112ms460 KiB
36Elfogadva1/113ms456 KiB
37Elfogadva1/113ms464 KiB
38Elfogadva1/113ms316 KiB
39Elfogadva1/110ms460 KiB
40Elfogadva1/17ms464 KiB