Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Help needed with Tree Matching problem on CSES!

Revision en1, by qwerty29, 2020-04-04 12:12:57

Problem statement: https://cses.fi/problemset/task/1130/
You are given a tree consisting of n nodes.
A matching is a set of edges where each node is an endpoint of at most one edge. What is the maximum number of edges in a matching?

My Approach:
1) Run BFS to find the bipartite partition for the given tree.
2) We iterate over the number of nodes in the maximum of the above sets.
3) Since every node in this set will have a corresponding node in the other set we can choose this node edge in our answer.
4) while taking the nodes in this set we have to make sure that its neighboring node is only visited once i.e. other nodes in this set cannot share a node in the other set.

#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<vector<int> > graph(n+1);
    
    for(int i=0;i<n-1;++i){
        int a,b; cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    queue<int> q;
    vector<int> color(n+1);
    vector<int> visited(n+1,0);

    q.push(1);
    color[1] = 0;
    visited[1] = 1;
    while(!q.empty()){
        int node = q.front(); q.pop();
        for(int i:graph[node]){
            if(!visited[i]){
                visited[i] = 1;
                color[i] = (color[node]+1)%2;
                q.push(i);
            }
        }
    }
    vector<int> first;
    vector<int> second;
    for(int i=1;i<=n;++i){
        if(color[i]==0) first.push_back(i);
        else second.push_back(i);
    }
    int count = 0;
    fill(all(visited),0);
    if(first.size() < second.size()) swap(first,second);
    for(int i=0;i<first.size();++i) {
        visited[first[i]] = 1;
        for(int it:graph[first[i]]){
            if(!visited[it]){
                visited[it] = 1;
                count++;
                break;
            }
        }
    }
    cout << count << '\n';
    return 0;
}

Am I going in the right direction for this problem since I am new to this concept?
Thank you!.

Tags #trees, matching

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English qwerty29 2020-04-04 12:12:57 2206 Initial revision (published)