CSES Tree Algorithms: 2. Maximum Matching

CSES Tree Algorithms

2. Maximum Matching

link

	#include<bits/stdc++.h>
	using namespace std;
	class Graph{
	vector<int>*adj;
	int n;
	public:
	Graph(int n){
	n=n+1;
	this->n=n;
	adj=new vector<int>[n];
	}
	void addEdge(int u,int v){
	adj[u].push_back(v);
	adj[v].push_back(u);
	}
	vector<int>* adjList(){
	return adj;
	}
	};
	void dfs(vector<int>*adj,int u,vector<int>&vis,int par,vector<int>&parArr,vector<pair<int,int>>&edg){
	if(vis[u])return;
	vis[u]=1;
	for(auto v:adj[u])
	dfs(adj,v,vis,u,parArr,edg);
	if(par==-1)return;
	if(parArr[u]!=parArr[par])return;
	if(parArr[u] && parArr[par])return;
	parArr[u]=parArr[par]=1;
	edg.push_back({u,par});
	}
	int main(){
	system("CLS");
	int n;cin>>n;
	Graph g(n);
	for(int i=0;i<n-1;++i){
	int a,b;cin>>a>>b;
	g.addEdge(a,b);
	}
	vector<int>*adj= g.adjList();
	vector<int>vis(n+1,0),vis2(n+1,0);
	vector<int>parArr(n+1,0);
	vector<pair<int,int>>edg;
	dfs(adj,1,vis,-1,parArr,edg);
	cout<<edg.size();
	return 0;
	};

view raw maximumMatching hosted with ❤ by GitHub