1133F1. Spanning Tree with Maximum Degree - Codeforces Solution C++

➤  Problem Link : 1133F1. Spanning Tree with Maximum Degree 

✅ C++ Solution :

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

#define ll long long int
#define pp pair<int,int>
#define mp make_pair

int n,m;

pp arr[200001];

int deg[200001];
int par[200001];

int find(int v)
{
    if(par[v]==v)
        return v;
    
    return par[v]=find(par[v]); 
}


int main()
{
	cin>>n>>m;
	int mx=1;
	for(int i=0;i<n;i++)
	{
		deg[i]=0;
		par[i]=i;
	}
	for(int i=0;i<m;i++)
	{
		cin>>arr[i].first>>arr[i].second;
		deg[arr[i].first]++;
		deg[arr[i].second]++;
		if(deg[arr[i].first] > deg[mx])
			mx=arr[i].first;
		if(deg[arr[i].second] > deg[mx])
			mx=arr[i].second;
	}
	int p1,p2;
	for(int i=0;i<m;i++)
	{
		if(arr[i].first==mx)
			par[arr[i].second]=arr[i].first;
		else if(arr[i].second==mx)
			par[arr[i].first]=arr[i].second;
		else
			continue;
		cout<<arr[i].first<<" "<<arr[i].second<<"\n";
	}

	for(int i=0;i<m;i++)
	{
		if(arr[i].first==mx || arr[i].second==mx)
			continue;
		p1=find(arr[i].first);
		p2=find(arr[i].second);
		if(p1!=p2)
		{
			cout<<arr[i].first<<" "<<arr[i].second<<"\n";
			par[p2]=p1;
		}
	}




}

 

Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook. 

😇Happy Learning!!

• Tweet
• Share
• Share
• Share
• Share

About Utkarsh Gupta

I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.