2273 2023. 01. 09 07:33:36 bzsofia Legtávolabbi leszármazott cpp11 Elfogadva 50/50 94ms 17860 KiB
// Legtavolabbi rokon.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct adat
{
    int tav;
    vector <int> sz;
    bool lat, gyerek;
};

int i, maxt, akt, maxi, n, a, b, kezd;
queue <int> s;

int main()
{
    cin >> n;
    vector <adat> x(n + 1);

    for (i = 1; i < n; ++i)
    {
        cin >> a >> b;
        x[a].sz.push_back(b);
        x[b].sz.push_back(a);
        x[b].gyerek = 1;
    }

    for (i = 1; i <= n; ++i)
    {
        if (!x[i].gyerek)
        {
            kezd = i;
            break;
        }
    }

    x[kezd].lat = 1;
    x[kezd].tav = 0;
    s.push(kezd);
    while (!s.empty())
    {
        akt = s.front();
        s.pop();
        for (auto& e : x[akt].sz)
        {
            if (!x[e].lat)
            {
                x[e].lat = 1;
                x[e].tav = x[akt].tav + 1;
                s.push(e);
            }
        }
    }

    for (i = 1; i <= n; ++i)
    {
        if (x[i].tav > maxt)
        {
            maxt = x[i].tav;
            maxi = i;
        }
    }

    cout << maxi;

    return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1808 KiB
2 Elfogadva 0/0 83ms 14920 KiB
3 Elfogadva 1/1 2ms 2304 KiB
4 Elfogadva 3/3 2ms 2380 KiB
5 Elfogadva 3/3 2ms 2416 KiB
6 Elfogadva 1/1 2ms 2620 KiB
7 Elfogadva 1/1 2ms 2700 KiB
8 Elfogadva 1/1 3ms 3020 KiB
9 Elfogadva 2/2 87ms 17324 KiB
10 Elfogadva 3/3 86ms 17440 KiB
11 Elfogadva 3/3 2ms 3452 KiB
12 Elfogadva 4/4 93ms 17264 KiB
13 Elfogadva 4/4 90ms 17320 KiB
14 Elfogadva 3/3 9ms 4540 KiB
15 Elfogadva 3/3 85ms 15972 KiB
16 Elfogadva 3/3 79ms 15520 KiB
17 Elfogadva 3/3 86ms 16596 KiB
18 Elfogadva 4/4 63ms 13472 KiB
19 Elfogadva 4/4 75ms 15260 KiB
20 Elfogadva 4/4 94ms 17860 KiB