25D. Roads not only in Berland - Codeforces Solution C++

➤  Problem Link : 25D. Roads not only in Berland 

✅ C++ Solution :

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

#define ll long long int

#define pp pair<int,int>
#define mp make_pair
#define pb push_back

int par[1001];
int n;

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

int main()
{
	int p1,p2,a,b;
	cin>>n;
	for(int i=1;i<=n;i++)
		par[i]=i;
	vector<pp> rem;
	for(int i=1;i<=n-1;i++)
	{
		cin>>a>>b;
		p1=find(a);
		p2=find(b);
		if(p1!=p2)
			par[p2]=p1;
		else
			rem.pb(mp(a,b));
	}
	int prev=-1,k=0;
    cout<<rem.size()<<"\n";
    for(int i=1;i<=n;i++)
    {
		if(par[i]==i)
    	{
    		if(prev!=-1)
    		{
    			cout<<rem[k].first<<" "<<rem[k].second<<" "<<prev<<" "<<i<<"\n";
    			k++;
    		}
    		prev=i;
    	}
    }
	



}

 

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.