157112025-02-23 15:05:12SRobKerékpártúra (50 pont)cpp17Hibás válasz 46/50118ms2356 KiB
// kerekparTura_NT_kat2_ford2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graf;
vector<int> mikorVoltunkItt; /*a: 1.
                               b: 2.*/
vector<bool> jok; // megoldásként jó, tehát pl az ábrán az 1-es csúcs. Nem elérhető, de jó megoldás
vector<bool> elerheto; // elérhető és jó megoldás is ezáltal
int Kkezdo;
void DFS(int csucs, int lepes)
{
    int szomszed;
    mikorVoltunkItt[csucs] = lepes;
    for (int i = 0; i < graf[csucs].size(); i++)
    {
        szomszed = graf[csucs][i];
        if (mikorVoltunkItt[szomszed] == -1)
        {
            DFS(szomszed, lepes + 1);
        }
        else if (mikorVoltunkItt[szomszed] != -1 &&
                 elerheto[szomszed] &&
                 mikorVoltunkItt[szomszed] != lepes-1)
        {
            elerheto[csucs] = true;
        }
    }

    for (int i = 0; i < graf[csucs].size(); i++)
    {
        szomszed = graf[csucs][i];
        if (elerheto[szomszed])
        {
            elerheto[csucs] = true;
        }
    }
    if (elerheto[csucs])
    {
        for (int i = 0; i < graf[csucs].size(); i++)
        {
            if (graf[csucs][i] != Kkezdo)
            {
                jok[graf[csucs][i]] = true;
            }
            
        }
    }
}
int main()
{
#pragma region beolvasás



    int Ncsucs, Mel;
    cin >> Ncsucs >> Mel >> Kkezdo;
    graf.resize(Ncsucs+1); // 0. csucsot nem veszem figyelembe
                            // azt adja meg, hogy belőle hova lehet menni
    mikorVoltunkItt.resize(Ncsucs + 1);
    jok.resize(Ncsucs + 1);
    elerheto.resize(Ncsucs + 1);
    int seged1, seged2;
    for (int i = 0; i < Mel; i++)
    {
        cin >> seged1 >> seged2;
        graf[seged1].push_back(seged2);

    }
   /* for (int i = 0; i < graf.size(); i++)
    {
        cout << i  << ".: ";
        for (int j = 0; j < graf[i].size(); j++)
        {
            cout << graf[i][j] << " ";
        }
        cout << endl;
    }*/
#pragma endregion

#pragma region elokeszulet



    for (int i = 1; i <= Ncsucs; i++)
    {
        mikorVoltunkItt[i] = -1;
        jok[i] = false;
        elerheto[i] = false;
    }

    elerheto[Kkezdo] = true;
    DFS(Kkezdo, 1);
    //cout << "jok: " << endl;
    int joDb = 0;
    for (int i = 1; i <= Ncsucs; i++)
    {
        if (jok[i])
        {
            joDb++;
        }
    }
    if (joDb > 0)
    {
        cout << joDb << endl;
        for (int i = 1; i <= Ncsucs; i++)
        {
            if (jok[i])
            {
                cout << i << " ";
            }
        }
    }
    else
    {
        cout << "0";
    }
    
#pragma endregion
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base46/50
1Elfogadva0/01ms508 KiB
2Elfogadva0/018ms1076 KiB
3Hibás válasz0/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/21ms380 KiB
8Elfogadva2/22ms316 KiB
9Hibás válasz0/23ms316 KiB
10Elfogadva2/23ms316 KiB
11Elfogadva2/24ms556 KiB
12Elfogadva2/210ms504 KiB
13Elfogadva2/29ms532 KiB
14Elfogadva2/218ms508 KiB
15Elfogadva3/330ms1624 KiB
16Elfogadva4/434ms1836 KiB
17Elfogadva4/448ms1844 KiB
18Elfogadva3/343ms1784 KiB
19Elfogadva3/335ms1812 KiB
20Elfogadva3/3105ms2356 KiB
21Elfogadva3/3118ms2356 KiB
22Elfogadva3/3118ms2356 KiB