fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <set>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 100100;
  9.  
  10. set<int> adj[maxn];
  11. int grau[maxn];
  12. queue<pair <int,int> > q[2];
  13.  
  14.  
  15. int main(){
  16. 	int n;
  17. 	int sz;
  18. 	scanf("%d",&n);
  19. 	sz=n;
  20. 	for(int i=0;i<n-1;i++){
  21. 		int a,b;
  22. 		scanf("%d %d",&a,&b);
  23. 		a--,b--;
  24. 		grau[a]++;
  25. 		grau[b]++;
  26. 		adj[a].insert(b);
  27. 		adj[b].insert(a);
  28. 	}
  29. 	for(int i=0;i<n;i++){
  30. 		if(grau[i]==1){
  31. 			q[0].push(make_pair(i,0));
  32. 		}
  33. 	}
  34. 	int resp=0;
  35. 	int x=0;
  36. 	while(!q[0].empty()||!q[1].empty()){
  37. 		if(x==0&&sz<=2)break;
  38. 		int fi=q[x].front().first;
  39. 		int se=q[x].front().second;
  40. 		if(se)resp++;
  41. 		q[x].pop();
  42. 		sz--;
  43. 		for(set<int>::iterator it=adj[fi].begin();it!=adj[fi].end();it++){
  44. 			grau[*it]--;
  45. 			grau[fi]--;
  46. 			adj[*it].erase(fi);
  47. 			if(grau[*it]==1){
  48. 				q[x^1].push(make_pair(*it,se^1));
  49. 			}
  50. 		}
  51. 		adj[fi].clear();
  52. 		if(q[x].empty())x^=1;
  53. 	}
  54. 	if(sz==2)resp++;
  55. 	printf("%d\n",resp);
  56. }
  57.  
Success #stdin #stdout 0s 6156KB
comments (?)
stdin
copy 
2
1 2
stdout
copy 
1
https://ideone.com/0jJZZR
language:
C++14 (gcc 8.3)
created:
8 years 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!