fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define MAXI 10000001
  6. vector<int>height(MAXI);
  7.  
  8. void dfs(int node,vector<vector<int>>graph,vector<bool>&visited,vector<int>&parent){
  9. 	visited[node]=true;
  10.  
  11. 	for(auto it:graph[node]){
  12. 		if(!visited[it]){
  13. 			parent[it]=node;
  14. 			dfs(it,graph,visited,parent);
  15. 		}
  16. 	}
  17.  
  18. 	int h=0;
  19.  
  20. 	for(auto it: graph[node]){
  21. 		if(it==parent[node]){
  22. 			//ignore
  23. 		}
  24.  
  25. 		else{
  26. 			h=max(h,height[it]);
  27. 		}
  28.  
  29. 	}
  30.  
  31. 	height[node]=1+h;
  32. }
  33.  
  34. int main(){
  35. 	int n;
  36. 	cin>>n;
  37.  
  38. 	vector<vector<int>>graph(n);
  39. 	int i=1;
  40. 	int m=n-1;
  41.  
  42. 	while(i<=m){
  43. 		int x,y;
  44. 		cin>>x>>y;
  45. 		x--,y--;
  46. 		graph[x].push_back(y);
  47. 		graph[y].push_back(x);
  48.  
  49. 		i++;
  50. 	}
  51.  
  52. 	vector<bool>visited(n,false);
  53. 	vector<int>parent(n,-1);
  54.  
  55.  
  56. 	dfs(0,graph,visited,parent);
  57. 	for(int i=0;i<n;i++){
  58. 		cout<<"Height of node "<<i+1<<" : "<<height[i]<<endl;
  59. 	}
  60.  
  61. 	return 0;
  62.  
  63.  
  64. }
Success #stdin #stdout 0.01s 42224KB
comments (?)
stdin
copy 
5
1 2
2 3 
3 4 
1 5
stdout
copy 
Height of node 1 : 4
Height of node 2 : 3
Height of node 3 : 2
Height of node 4 : 1
Height of node 5 : 1
https://ideone.com/XDKoXN
language:
C++ (gcc 8.3)
created:
3 days 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!