954D. Fight Against Traffic - Codeforces Solution C++ ~ CodingWithArt

➤ Problem Link : 954D. Fight Against Traffic

✅ C++ Solution :

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

#define ll long long int

bool visited[1001];

int disS[1001];
int disT[1001];

void bfs(int src, unordered_set<int> adj[], int n, bool key)
{
	memset(visited,0,n+1);
	visited[src]=1;
	if(!key)
		disS[src]=0;
	else
		disT[src]=0;
	queue<int> q;
	q.push(src);
	int v;
	while(!q.empty())
	{
		int v = q.front();
		q.pop();
		for(auto it = adj[v].begin(); it!=adj[v].end(); it++)
		{
			if(!visited[*it])
			{
				visited[*it]=1;
				if(!key)
					disS[*it]=disS[v]+1;
				else
					disT[*it]=disT[v]+1;

				q.push(*it);
			}
		}
	}
}

int main()
{
	int n,m,s,t,u,v,ans=0;
	cin>>n>>m>>s>>t;
	unordered_set<int> adj[n+1];
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v;
		adj[u].insert(v);
		adj[v].insert(u);
	}

	bfs(s,adj,n,0);

	bfs(t,adj,n,1);
    
 //   for(int i=1;i<=n;i++)
   //     cout<<disS[i]<<" "<<disT[i]<<endl;
    
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(adj[i].find(j)!=adj[i].end())
				continue;

			if((disS[i] + disT[j] + 1 >= disS[t]) && (disS[j] + disT[i] +1 >= disS[t]))
				ans++;
		}
	}

	cout<<ans;


}

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.