CSES Tree Algorithms

	#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

	#include<bits/stdc++.h>
	using namespace std;

	int help(vector<vector<int>>&tr,int u,vector<int>&dp){

	if(dp[u]!=-1)return dp[u];
	int c=0;
	for(auto v:tr[u]){
	c+= (1+help(tr,v,dp));
	}
	return dp[u]=c;
	}


	int main(){
	system("CLS");

	int n;cin>>n;
	vector<int>v(n-1);
	for(auto &it:v)cin>>it;

	vector<vector<int>>tr(n+1);

	for(int i=0;i<n-1;++i){
	tr[v[i]].push_back(i+2);
	}

	vector<int>ans;
	vector<int>dp(n+1,-1);
	for(int i=1;i<=n;++i){
	int k=help(tr,i,dp);
	ans.push_back(k);
	}
	for(auto it:ans)
	cout<<it<<" ";



	return 0;
	};

view raw subordinates hosted with ❤ by GitHub

Friday, 28 October 2022