215282026-01-13 11:47:16algoproLegtávolabbi leszármazottcpp17Elfogadva 50/50105ms10548 KiB
// UUID: 236743bc-a3ef-43b3-a50c-3c6a90a6ef42
#include <bits/stdc++.h>
#include <sys/types.h>
using namespace std;

vector<vector<int>> g;
vector<int> distance_from_root;// also tracks whether node was visited (if not -1 for the index)


void dfs(int p, int d){
	distance_from_root[p] = d; // visit p
	for(int c:g[p]){ // for each child of p
		if (distance_from_root[c] == -1){ // if c not visited
			dfs(c, d+1);
		}
	}

}

int main() {
	int n;
	cin >> n;

	vector<bool> root_candidates(n+1, true);
	g.resize(n+1, vector<int>());
	for (int i=0;i<n-1;i++){
		int from, to;
		cin >> from  >> to;
		g[from].push_back(to);
		root_candidates[to] = false;
	}
	int root = -1;
	for (int j=1;j<=n;j++){
		if(root_candidates[j]){
			if(root!= -1){
				cout << "error: multiple roots found!\n";
			}
			root = j;
		}
	}
	if (root == -1){
		cout << "error: root not found!\n";
	}

	// cout << "the root is " << root << "\n";

	distance_from_root.resize(n+1,-1);

	// cout << "graph:\n";
	// for(int p =1; p<=n; p++){
	// 	cout << p << ":\n\t";
	// 	for (int c: g[p]) cout << c << " " ;
	// 	cout << "\n";
	// }

	dfs(root, 0);

	// cout << "distances:\n";
	// for(int d: distance_from_root){
	// 	cout << d << " ";
	// }
	// cout << "\n";

	int max_idx = 0;
	int max_d = distance_from_root[0];
	for (int i=0;i<=n;i++){
		if(distance_from_root[i] > max_d){
			max_d = distance_from_root[i];
			max_idx = i;
		}
	}

	cout << max_idx;
	






}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/082ms4144 KiB
3Elfogadva1/11ms500 KiB
4Elfogadva3/31ms508 KiB
5Elfogadva3/31ms316 KiB
6Elfogadva1/11ms316 KiB
7Elfogadva1/11ms316 KiB
8Elfogadva1/11ms388 KiB
9Elfogadva2/285ms4700 KiB
10Elfogadva3/383ms4704 KiB
11Elfogadva3/31ms316 KiB
12Elfogadva4/490ms7272 KiB
13Elfogadva4/494ms7344 KiB
14Elfogadva3/38ms820 KiB
15Elfogadva3/383ms7220 KiB
16Elfogadva3/390ms7544 KiB
17Elfogadva3/387ms7052 KiB
18Elfogadva4/468ms5684 KiB
19Elfogadva4/475ms6604 KiB
20Elfogadva4/4105ms10548 KiB