11172022-03-03 23:50:48peti1234Legtávolabbi leszármazottcpp14Elfogadva 50/5067ms33364 KiB
#include <bits/stdc++.h>

using namespace std;
const int c=100005;
int n, szint[c];
vector<int> sz[c];
bool f[c];
void dfs(int a) {
    // egy melysegi bejarassal rekurzivan mindnekire ki lehet szamolni azt, hogy milyen tavoli utod
    for (auto x:sz[a]) {
        szint[x]=szint[a]+1;
        dfs(x);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i=1; i<n; i++) {
        int a, b;
        cin >> a >> b;
        sz[a].push_back(b);
        f[b]=1;
    }
    // az a kozos os, aki senkinek sem fia a listan (sosem szerepelt a masodik sorban)
    for (int i=1; i<=n; i++) {
        if (!f[i]) {
            dfs(i);
        }
    }
    // minimum kivalasztas
    int p=1;
    for (int i=1; i<=n; i++) {
        if (szint[i]>szint[p]) {
            p=i;
        }
    }
    cout << p << "\n";
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/04ms6472 KiB
2Elfogadva0/039ms11352 KiB
3Elfogadva1/13ms7620 KiB
4Elfogadva3/33ms7620 KiB
5Elfogadva3/33ms7620 KiB
6Elfogadva1/13ms7624 KiB
7Elfogadva1/13ms7632 KiB
8Elfogadva1/14ms7664 KiB
9Elfogadva2/237ms12944 KiB
10Elfogadva3/343ms14064 KiB
11Elfogadva3/33ms9920 KiB
12Elfogadva4/450ms20528 KiB
13Elfogadva4/446ms21684 KiB
14Elfogadva3/37ms12648 KiB
15Elfogadva3/343ms22976 KiB
16Elfogadva3/343ms24900 KiB
17Elfogadva3/350ms24764 KiB
18Elfogadva4/432ms22744 KiB
19Elfogadva4/439ms26244 KiB
20Elfogadva4/467ms33364 KiB