Link : https://cses.fi/problemset/task/1130/ My approach : 1. using dfs I going down if leaf node encounter then take it if its parent is not visited and mark both of them visited.
- If lets all child is giving answer and if any one of the child is not visited and parent is not visited increment count by 1 and mark them visited.
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,vector<int>>mp;
int dfs(int i,int prev,vector<int>&visited){
if(mp[i].size()==0){
// case 1 leaf case
if(prev != -1 && !visited[i] && !visited[prev]){
visited[i] = 1;
visited[prev]= 1;
return 1;
}
return 0;
}
int cal = 0;
int p = -1;
for(auto x : mp[i]){
cal += dfs(x,i,visited);
if(!visited[x]){
p = x;
}
}
// case 2 for non leaf case
if(p != -1 && !visited[p]){
if(!visited[i] && !visited[p]){
cal++;
visited[i] = 1;
visited[p] = 1;
}
}
return cal;
}
void solve(){
int n ;
cin>>n;
for(int i = 1;i<=n-1;i++){
int a,b;
cin>>a>>b;
mp[a].push_back(b);
}
vector<int>visited(n+1,0);
int ans = 0;
for(int i= 1;i<=n;i++){
int prev = -1;
if(!visited[i]){
ans += dfs(i,prev,visited);
}
}
cout<<ans<<endl;
}
void template1(){
int t;
cin>>t;
while(t>0){
solve();
t--;
}
}
void template2(){
solve();
}
int main(){
// template1();
template2();
return 0;
}