### qwerty29's blog

By qwerty29, history, 13 months ago,

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

• +4

 » 13 months ago, # |   0 It would be great if someone could help out to get solution for this problem
 » 13 months ago, # | ← Rev. 2 →   0 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 nodedp[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.
•  » » 10 months ago, # ^ |   0 thank you! very helpful
•  » » 10 months ago, # ^ |   0 @popabogdannnn can you show your code? My implementation failed based on your idea.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 I implemented this solution before coming here but getting 3 test cases wrong including 1 TLE, but I am more concerned about WA right now. Can someone spot out the error in mine? #include #include #include #define pb push_back using namespace std; map> m; vector visited; vector> dp; int countMatches(int currNode, int include) { if(dp[currNode][include] > 0) return dp[currNode][include]; /* * If include = 1, we include the current node else we exclude it. */ dp[currNode][include] = 0; visited[currNode] = true; if(include == 0) { for(int i: m[currNode]) { if(!visited[i]) { if(m[i].size() > 1) dp[currNode][include] += max(countMatches(i, 0), countMatches(i, 1)); } } } else { for(int i: m[currNode]) { if(visited[i]) continue; int k = 1 + (m[i].size() > 1? countMatches(i, 0): 0); for(int j: m[currNode]) { if(j == i) continue; if(!visited[j]) if(m[j].size() > 1) k += max(countMatches(j, 0), countMatches(j, 1)); } dp[currNode][include] = max(dp[currNode][include], k); } } visited[currNode] = false; return dp[currNode][include]; } int initiater() { return max(countMatches(1, 1), countMatches(1, 0)); } int main() { int n; cin >> n; int x, y; dp = vector>(n+1, vector(2, -1)); visited = vector(n, false); for(int i=0; i> x >> y; m[x].pb(y); m[y].pb(x); } cout << initiater(); } 
•  » » 8 months ago, # ^ |   0 dp[node][0] = sum( dp[son][1] ) also works. Why is this greedy decision working?
•  » » » 5 months ago, # ^ |   0 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]
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 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 g; vector visited;void dfs(ll src,ll par){ for(auto nbr:g[src]){ if(nbr != par) dfs(nbr,src); } // cout<>n; g = vector>(n + 1); visited = vector(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<
 » 12 months ago, # | ← Rev. 2 →   0 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 3if you algo chooses 1 3Here is my solution using Hopkraft_karp Code Maximum Matching#include using namespace std; // #define int long long int #define vec vector #define pb push_back #define s(x) scanf("%d",&x) #define all(x) x.begin(),x.end() #define pii pair #define fi first #define se second #define mod 1000000007 #define SZ 400005 #define endl "\n" #define trace(x) cerr << #x << ": " << x << endl #define boost ios::sync_with_stdio(0);cin.tie(0) int x, u, v; vec adj_inp[200001]; ///////////////////////////////////////////////// #define NIL 0 #define INF (1<<28) vector< int > adj[SZ]; int n, m, match[SZ], dist[SZ]; // n: number of nodes on left side, nodes are numbered 1 to n // m: number of nodes on right side, nodes are numbered n+1 to n+m // adj = NIL[0] ∪ adj1[adj[1---n]] ∪ adj2[adj[n+1---n+m]] bool bfs() { int i, u, v, len; queue Q; for(i=1; i<=n; i++) { if(match[i]==NIL) { dist[i] = 0; Q.push(i); } else dist[i] = INF; } dist[NIL] = INF; while(!Q.empty()) { u = Q.front(); Q.pop(); if(u!=NIL) { for(int v: adj[u]) { if(dist[match[v]]==INF) { dist[match[v]] = dist[u] + 1; Q.push(match[v]); } } } } return (dist[NIL]!=INF); } bool dfs(int u) { int i, v, len; if(u!=NIL) { for(int v: adj[u]) { if(dist[match[v]]==dist[u]+1) { if(dfs(match[v])) { match[v] = u; match[u] = v; return true; } } } dist[u] = INF; return false; } return true; } int hopcroft_karp_max_match() { int matching = 0, i; // match[] is assumed NIL for all vertex in adj while(bfs()) for(i=1; i<=n; i++) if(match[i]==NIL && dfs(i)) matching++; return matching; } void print_matching() { for(int i = 1; i <=n ; i++) { if(match[i] != NIL) cout << i << " " << match[i]-n << endl; } } void make_bipartite_dfs(int u, int p, int l) { if(l%2 and p != -1) { adj[u].pb(p+n); adj[p+n].pb(u); } for(int v: adj_inp[u]) { if(v!=p) { if(l%2) { adj[u].pb(v+n); adj[v+n].pb(u); } make_bipartite_dfs(v, u, l+1); } } } void purple() { cin >> n; for(int i = 0; i < n-1; i++) { cin >> u >> v; adj_inp[u].pb(v); adj_inp[v].pb(u); } make_bipartite_dfs(1, -1, 1); cout << hopcroft_karp_max_match() << endl; } signed main() { boost; int t=1; while(t--) purple(); } 
 » 9 months ago, # |   0 One of solutions that I found searching online, Maybe related to what @popabogdannn said ? #include #include using namespace std; typedef vector vi; typedef vector vvi; int n, a, b; vi dp1, dp2; vvi g; void dfs(int u, int p) { for (auto z:g[u]) { if (z == p) continue; dfs(z, u); dp2[u] += max(dp1[z], dp2[z]); } for (auto z:g[u]) { if (z == p) continue; dp1[u] = max(dp1[u], 1 + dp2[u] + dp2[z] - max(dp1[z], dp2[z])); } } int main() { cin >> n; dp1 = vi(n); dp2 = vi(n); g = vvi(n); for (int i = 0; i < n - 1; i++) { cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } dfs(0, 0); cout << max(dp1[0], dp2[0]) << endl; } 
•  » » 7 months ago, # ^ | ← Rev. 6 →   -6 Nice Solution.