Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

qwerty29's blog

By qwerty29, history, 2 months ago, In English,

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!.

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be great if someone could help out to get solution for this problem

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This problem is best solved with DP. First, you should choose a node as a root for the given tree. For the sake of simplicity, you may choose node 1 as your root. Then calculate the following dp[node][taken] = the maximum number of matches you can obtain in the subtree with root node, where taken is 1 if you included node in a matching, 0 if not. The recurrence is:

dp[node][0] = sum(max(dp[son][0], dp[son][1])) where son is a direct son of node

dp[node][1] = max(1 + dp[son][0] + sum(max(dp[son2][0], dp[son2][1])) where son2 is a son of node, and son2 != son) where son is a son of node.

Feel free to ask me if you have further questions on this.

»
4 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You are not going in right direction. You need to use a maximum matching algorithm like hopkraft_karp. Your algo will fail in cases like this:

4
1 3
1 4
2 3

if you algo chooses 1 3

Here is my solution using Hopkraft_karp

Code Maximum Matching