Link : [https://cses.fi/problemset/task/1130/](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.↵
↵
↵
2. 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;↵
}↵
~~~~~↵
↵
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.↵
↵
↵
2. 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;↵
}↵
~~~~~↵
↵
