fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1E5+2;
  5. int n;
  6. int ans = 0;
  7. vector<vector<int> > g;
  8. vector<int> par(MAXN, -1);
  9. vector<bool> used(MAXN, 0);
  10. vector<int> s;
  11.  
  12. void bfs(){
  13. 	queue<int> q; q.push(0);
  14. 	while(!q.empty()){
  15. 		int u = q.front(); q.pop();
  16. 		s.push_back(u);
  17. 		for(int v : g[u]){
  18. 			if(v!= par[u]){
  19. 				par[v] = u;
  20. 				q.push(v);
  21. 			}
  22. 		}
  23. 	}
  24. }
  25.  
  26. int main() {
  27. 	cin >> n; g.assign(n, vector<int>());
  28. 	for(int i=1; i< n; ++i){
  29. 		int u, v; cin >> u  >> v; --u;  --v;
  30. 		g[u].push_back(v);
  31. 		g[v].push_back(u);
  32. 	}
  33. 	bfs();
  34. 	for(int i= n-1; i>=0; --i){
  35. 		if(used[s[i]]) continue;
  36. 		if(par[s[i]]!= -1 && !used[par[s[i]]]){
  37. 			++ans;
  38. 			used[s[i]] = used[par[s[i]]] = 1;
  39. 		}
  40. 	}
  41. 	cout << ans;
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 4212KB
comments (?)
stdin
copy 
3 
1 2
2 3
stdout
copy 
1
https://ideone.com/CeWhlr
problem PT07X, based on SPOJ submission 24476060 (CPP14), 2019-09-27 15:26:43
language:
C++14 (gcc 8.3)
created:
4 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!