fork download 
  1. #include<iostream>
  2. #include <queue>
  3. #define ll long long int 
  4. using namespace std;
  5. int main(){
  6. 	ll n,r,c;
  7. 	cin>>n;
  8. 	ll g[n][n],visited[n],lastnode,sum=0,a,b;
  9. 	for(ll i=0;i<n;i++)
  10. 		for(ll j=0;j<n;j++)
  11. 			if(i==j)
  12. 				g[i][j]=0;
  13. 			else	
  14. 				g[i][j]=-1;
  15. 	for(ll i=0;i<n-1;i++){
  16. 		cin>>a>>b;
  17. 		g[a-1][b-1]=1;
  18. 		g[b-1][a-1]=1;
  19. 	}
  20. 	for(ll i=0;i<n;i++)
  21. 		visited[i]=0;
  22. 	queue<ll> q;
  23. 	q.push(0);
  24. 	visited[0]=1;
  25. 		while(!q.empty()){
  26. 	    	r=q.front();
  27. 			q.pop();
  28. 			for(ll i=0;i<n;i++)
  29. 				if(g[r][i]==1 && !visited[i]){
  30. 					q.push(i);
  31. 					visited[i]=1;
  32. 				}
  33. 	}
  34. 	lastnode=r;
  35. 	for(ll i=0;i<n;i++)
  36. 		visited[i]=0;
  37. 	visited[r]=1;
  38. 	q.push(r);
  39. 	while(!q.empty()){
  40. 		lastnode=q.front();
  41. 		q.pop();
  42. 		c=0;
  43. 		for(ll i=0;i<n;i++)
  44. 			if(g[lastnode][i]==1 && !visited[i]){
  45. 				if(c==0){
  46. 					sum++;
  47. 					c=1;
  48. 				}
  49. 				visited[i]=1;
  50. 				q.push(i);
  51. 				}
  52. 	}
  53. 	cout<<sum;
  54. 	return 0;
  55. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin 
10
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
9 10
stdout 
8
https://ideone.com/lnccis
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!