AKBAR - Akbar , The great - SPOJ Solution C++ ~ CodingWithArt

➤ Problem Link : AKBAR

👉 Hint : edit please

✅ C++ Solution :

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

#define ll long long int

vector<ll> adj[1000001];
ll Puttar[1000001];
ll cnt;
bool flag=0;
void Bfs(ll v,ll s,ll k)
{
    queue<pair<ll,ll> >q;
    q.push(make_pair(v,s));
    while(!q.empty())
    {
        ll v=q.front().first;
        ll s=q.front().second;
        q.pop();
        if(Puttar[v])
	    {
    	    if(Puttar[v]!=k)
    	    {
    	    
        	    flag=1;
        	    return;
    	    } 
    		continue;
    		
	    }
	    Puttar[v]=k;
	    cnt++;
	    if(s>0)
	    {
        	for(ll i=0;i<adj[v].size();i++)
        	{
                q.push(make_pair(adj[v][i],s-1));
        	}
    	}
        
    }
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
	    flag=0;
		cnt=0;
		memset(Puttar,0,sizeof(Puttar));
		memset(adj,0,sizeof(adj));
		ll n,r,m,a,b,k,s;
		cin>>n>>r>>m;
		while(r--)
		{
			cin>>a>>b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		while(m--)
		{
			cin>>k>>s;
			Bfs(k,s,k);
			if(flag)
			    break;
		}
	
		if(cnt!=n || flag)
			cout<<"No"<<endl;
		else
			cout<<"Yes"<<endl;
	}
}

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

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.