fork(1) download
copy 
  1.     #include<bits/stdc++.h>
  2.     using namespace std;
  3.     #define S(x) scanf("%lld", &x)
  4.     #define ll long long
  5.  
  6.     ll visit[100006] = {0},pre[100006] = {0},col[100006] = {0};
  7.     vector<int> v[100005];
  8.  
  9.     bool BPM(ll cu,ll seen[]) {
  10.     //	cout<<cu<<endl;
  11. 	    for(ll i = 0;i < v[cu].size();i++) {
  12. 	    	if(!seen[v[cu][i]]) {
  13. 	    		seen[v[cu][i]]= true;
  14. 	    		if(pre[v[cu][i]] < 0 || BPM(pre[v[cu][i]],seen)) {
  15. 	    			pre[v[cu][i]] = cu;
  16. 	    		//	cout<<v[cu][i]<<" "<<cu<<endl;
  17. 	    			return true;
  18. 	    		}
  19. 	    	}
  20. 	    }
  21.     	return false;
  22.     }
  23.  
  24.     void maxBPM(ll n)
  25.     {
  26.     	ll i;
  27.     	ll cnt = 0;
  28.     	for(i = 1;i <= n;i++) {
  29.     		ll seen[v[i].size() + 5];
  30.     		memset(seen,0,sizeof(seen));
  31.     		if(BPM(i,seen) && !col[i]) {
  32.     			cnt++;
  33.     		}
  34.     	}
  35.     	cout<<cnt<<"\n";
  36.     }
  37.  
  38.     void dfs(ll curr,ll dep) 
  39.     {
  40.     	if(visit[curr] == 0) {
  41.     		ll i;
  42.     		visit[curr] = 1;
  43.     		col[curr] = dep & 1;
  44.     		for(i=  0;i < v[curr].size();i++) {
  45.     			if(visit[v[curr][i]] == 0) {
  46.     				dfs(v[curr][i],dep+1);
  47.     			}
  48.     		}
  49.     	//	cout<<curr<<" "<<prev<<" "<<flag<<endl;
  50.     	}
  51.     	return ;
  52.     }
  53.  
  54.  
  55.  
  56.     int main()
  57.     {
  58.     	ll n;
  59.     	S(n);
  60.     	ll i;
  61.     	memset(pre,-1,sizeof(pre));
  62.     	for(i =0;i < n - 1;i++) {
  63.     		ll p,q;
  64.     		S(p);
  65.     		S(q);
  66.     		v[p].push_back(q);
  67.     		v[q].push_back(p);
  68.     	}
  69.     	dfs(1,0);
  70.     	maxBPM(n);
  71.     }
  72.  
Runtime error #stdin #stdout 0s 6948KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qN2zIU
language:
C++ (gcc 8.3)
created:
10 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!