qwerty29's blog

Help needed with Tree Matching problem on CSES!
By qwerty29, history, 5 years 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

Comments Comments (14)
| Write comment?
»
5 years 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

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you! very helpful

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @popabogdannnn can you show your code? My implementation failed based on your idea.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dp[node][0] = sum( dp[son][1] ) also works. Why is this greedy decision working?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You might have got it now but for finding dp[node][0], we are not considering the current node in any matching edge. Thus we can greedily pick the best from all nodes. That is dp[son][1]

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Yeah but this particular question can also be solved using a greedy approach. Just perform a postorder traversal i.e start with the leaf edges and go up to the root of the tree(whatever we choose it to be). I mean DP is good as we don't have to think much that whether it can be solved using greedy or not but if we carefully observe it can be solved using greedy. This is my solution please tell me if there will be some cases that will give WA as it passed on CSES.

    ll n,cnt; vector<vector> g; vector visited;

    void dfs(ll src,ll par){

    for(auto nbr:g[src]){
    if(nbr != par)
       dfs(nbr,src);
}

// cout<<src<<" "<<par<<endl;
if(visited[src] != true && visited[par] != true){
    if(par == 0)
       return;
    // cout<<src<<" "<<par<<endl;
    cnt++;
    visited[src] = visited[par] = true;
}

return;

    }

    void solve(){

    cin>>n;
g = vector<vector<ll>>(n + 1);
visited = vector<bool>(n + 1,false);
cnt = 0;
rep(i,n - 1){
    ll u,v;
    cin>>u>>v;

    g[u].pb(v);
    g[v].pb(u);
}

dfs(1,0);

cout<<cnt<<endl;

    }

    int main(){

    #ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif

fast;
ll t = 1;

while(t--){
    solve();
}

    }

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How this is passing, it is totally a wrong solution!

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Why do you think that this approach is wrong?
        Tell me if I am wrong:

        My convention: By colouring a node I mean one of the edges contain that node and the node is not left alone.

        Now, there are two possibilities: 1. Colour a node 2. Uncoloured
        1. Coloured: If we have to colour a particular node x, then why should we choose some other neighbour of x which is not a leaf node as a non-leaf node will disturb other nodes as well. In this case, if there is an edge to a leaf then we must take it.

        2. Uncoloured: If a node x is uncoloured and it has one leaf node as its neighbour then we can take one more edge, i.e, an edge between the leaf node and node x. It will not disturb other nodes.

        It is similar to topological ordering, where we take nodes having indegrees 0 first, then subtract the indegrees of all its neighbours by 1, if any of them becomes 0 then push it into the queue and continue.

        My code (Similar logic, implementation similar to Kahn's algorithm) : https://cses.fi/paste/052f635c07bfa51c26f96a/

        → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Code
    → Reply
»
4 years 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
→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is a nice problem, I've solved it before. Root the tree at an arbitrary node. Idea is to store $$$2$$$ arrays: $$$take[n]$$$ and $$$leave[n]$$$. Here $$$take[u]$$$ stores the number of edges you can take up into a matching of the subtree rooted at $$$u$$$, given that $$$u$$$ is present in the matching. $$$leave[u]$$$ is similarily defined, except that you do not take $$$u$$$. Now the transitions are simple. See my code for details: https://cses.fi/paste/7b6250d2bd69c63f20d838/

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why everyone overkilling this simple problem ?
code

→ Reply
»
6 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

just overkilling, root the tree and take a leaf and its parent to start, do it for every leaf whose parent isn't taken, after this, remove every taken edge, re-run the process until there is at most 1 vertex left, this can be achieved using a single dfs from the root

Code
→ Reply