22732023-01-09 07:33:36bzsofiaLegtávolabbi leszármazottcpp11Accepted 50/5094ms17860 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
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1808 KiB
2Accepted0/083ms14920 KiB
3Accepted1/12ms2304 KiB
4Accepted3/32ms2380 KiB
5Accepted3/32ms2416 KiB
6Accepted1/12ms2620 KiB
7Accepted1/12ms2700 KiB
8Accepted1/13ms3020 KiB
9Accepted2/287ms17324 KiB
10Accepted3/386ms17440 KiB
11Accepted3/32ms3452 KiB
12Accepted4/493ms17264 KiB
13Accepted4/490ms17320 KiB
14Accepted3/39ms4540 KiB
15Accepted3/385ms15972 KiB
16Accepted3/379ms15520 KiB
17Accepted3/386ms16596 KiB
18Accepted4/463ms13472 KiB
19Accepted4/475ms15260 KiB
20Accepted4/494ms17860 KiB