Needed help. Why my code is wrong for 5 testcase for CSES Problem for Tree Matching problem

Revision en2, by decrypt_me, 2023-07-13 15:49:13

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.

  1. 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;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English decrypt_me 2023-07-13 15:49:13 93
en1 English decrypt_me 2023-07-13 15:40:12 1857 Initial revision (published)