157102025-02-23 15:02:59SRobKerékpártúra (50 pont)cpp17Hibás válasz 0/50127ms2356 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++;
        }
    }
    cout << joDb <<endl;
    for (int i = 1; i <= Ncsucs; i++)
    {
        if (jok[i])
        {
            cout << i << " ";
        }
    }
#pragma endregion
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/50
1Hibás válasz0/01ms316 KiB
2Hibás válasz0/019ms1012 KiB
3Hibás válasz0/21ms316 KiB
4Hibás válasz0/21ms316 KiB
5Hibás válasz0/21ms316 KiB
6Hibás válasz0/21ms316 KiB
7Hibás válasz0/21ms316 KiB
8Hibás válasz0/22ms316 KiB
9Hibás válasz0/23ms316 KiB
10Hibás válasz0/24ms316 KiB
11Hibás válasz0/24ms456 KiB
12Hibás válasz0/212ms512 KiB
13Hibás válasz0/210ms564 KiB
14Hibás válasz0/219ms496 KiB
15Hibás válasz0/332ms1532 KiB
16Hibás válasz0/435ms1844 KiB
17Hibás válasz0/450ms2068 KiB
18Hibás válasz0/346ms1892 KiB
19Hibás válasz0/339ms1916 KiB
20Hibás válasz0/3114ms2356 KiB
21Hibás válasz0/3127ms2340 KiB
22Hibás válasz0/3127ms2356 KiB