fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void DFS(int source, vector<int> adjList[], vector<int> &parent, vector<int> &visited, vector<int> &heights){
  5. 	visited[source]=1;
  6. 	for(auto it : adjList[source]){
  7. 		if(!visited[it]){
  8. 			parent[it]=source;
  9. 			DFS(it, adjList, parent, visited, heights);
  10. 		}
  11. 	}
  12. 	int h=0;
  13. 	for(auto child : adjList[source]){
  14. 		//this means that child node is actually the parent
  15. 		if(child==parent[source]){
  16. 			//no op
  17. 		}
  18. 		else{
  19. 			h=max(h, heights[child]);
  20. 		}
  21. 	}
  22. 	heights[source]=1+h;
  23. }
  24.  
  25. int main() {
  26. 	int n;
  27. 	cin>>n;
  28. 	vector<int> adjList[n+1];
  29. 	vector<int> parent(n+1);
  30. 	vector<int> visited(n+1);
  31. 	vector<int> heights(n+1);
  32. 	for(int i=1;i<=n-1;i++){
  33. 		int x,y;
  34. 		cin>>x>>y;
  35. 		adjList[x].push_back(y);
  36. 		adjList[y].push_back(x);
  37. 	}
  38. 	DFS(1, adjList, parent, visited, heights);
  39. 	for(int i=1; i<=n; i++){
  40. 		cout<<"height of node "<<i<<" : "<<heights[i]<<"\n";
  41. 	}
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 5340KB
comments (?)
stdin
copy 
4
1 2
2 3
3 4
stdout
copy 
height of node 1 : 4
height of node 2 : 3
height of node 3 : 2
height of node 4 : 1
https://ideone.com/F2wY9k
language:
C++ (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!