11172022-03-03 23:50:48peti1234Legtávolabbi leszármazottcpp14Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/04ms6472 KiB
2Accepted0/039ms11352 KiB
3Accepted1/13ms7620 KiB
4Accepted3/33ms7620 KiB
5Accepted3/33ms7620 KiB
6Accepted1/13ms7624 KiB
7Accepted1/13ms7632 KiB
8Accepted1/14ms7664 KiB
9Accepted2/237ms12944 KiB
10Accepted3/343ms14064 KiB
11Accepted3/33ms9920 KiB
12Accepted4/450ms20528 KiB
13Accepted4/446ms21684 KiB
14Accepted3/37ms12648 KiB
15Accepted3/343ms22976 KiB
16Accepted3/343ms24900 KiB
17Accepted3/350ms24764 KiB
18Accepted4/432ms22744 KiB
19Accepted4/439ms26244 KiB
20Accepted4/467ms33364 KiB