PROBLEM LINK:
Setter- Adhyyan Sekhsaria
Tester- Adhyyan Sekhsaria
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY
PRE-REQUISITES:
BFS on a Graph, Pre-processing, Data Structures such as Vectors, Set &etc.
PROBLEM:
Given a graph of N nodes, we have to answer queries asking if there exists a node u at shortest distance of D from node 1, such that, the degree of node u is K. All the edges are of equal weight.
QUICK-EXPLANATION:
We run a BFS on a graph. Since edges are of equal weight, BFS is guaranteed to give shortest path. At every step, we keep track of two things-
- How far is this node from node 1? (i.e. number of levels b/w this node and node 1)
- Degree of this node.
Knowledge of STL (such as vectors or dynamic arrays) helps solve this question quickly.
EXPLANATION:
The editorial will consist of a single section only. Implementation will be integrated with explanation, the code being hidden under tabs. It is advised that you try out your own implementation first before peeking into editorial’s implementation for self-practice 
Full Solution-
Lets start the editorial with a very important concept. For graph where weights of ALL edges are equal, there are 2 things to note-
- BFS is sufficient to give correct answer.
- DFS FAILS to give shortest path.
It is very necessary to grasp and reason it. I will informally discuss the first point here, while second one will be in bonus corner for the interested.
Assuming you have an idea of what BFS is (refer to links in pre-requisites section elsewise), lets first observe what BFS does. Please fix node 1 as reference node for the below discussion.
BFS, in a way, traverses nodes “level-wise”. Meaning, first all nodes at level 1 are visited, then all nodes at level 2 are visited…and so on. How many edges do you need to go from one level to another? Just 1. We need just one edge to travel from a node at level k-1 to level k. (assuming they are directly connected/are neighbors). You can, also hence, get an intuition that no ‘unnecessary’ edges are picked. This is an informal intuition.
For the formal proof, we can see that because BFS is a level-wise traversal, AND all edges are equi-weighted (i.e. have same weight), we can see that it uses the “currently cheapest edge” to travel to an un-visited node. Thus, we can relate it to proof of Dijkstra’s Shortest Path Algorithm , which is guaranteed to give correct answer if all edges are positive.
Now, we know we have to do a BFS, what next?
Well, let me tell you something
The only difference between a solution which passes only first subtask (and TLE’s on the other) and the full solution is that, the full solution is smart. The inefficient solution will do a BFS for every query, while the efficient one will realize that in just a single BFS, we can get the data to answer any possible query.
How do we do that?
Please take time and get yourself introduced to set data-structure if you are new
We make an array of sets, say degree[d]. Here, degree[d] is the set which stores ALL degrees at distance of d from node 1. Now, after taking the input, for any node of degree b at distance d, we simply inset it at the appropriate set. This is as simple as doing - degree[d].insert(b);
Now, why set?
- Insertion and deletion of any element takes O(LogN) time.
- We can find if an element is present in a set in O(LogN) time.
- Duplicates are not allowed.
A implementation of modified BFS to pre-process data/store answers is given below. Try to have an attempt yourself first though!
Click to view
//Below is standard BFS algo. Note that BFS must be used for shortest path.
while(!que.empty())
{
temp=que.front();
que.pop();
u=temp.city;
degreeAtDistance[temp.distance].insert(arr[u].size());//Insert the degree of current node at
//distance =temp.distance
for(i=0;i<arr[u].size();i++)
{
if(!visited[arr[u][i]])
{
visited[arr[u][i]]=1;
b.city=arr[u][i];
b.distance=temp.distance+1;
que.push(b);
}
}
}
An example function to answer queries using above ideas is given below. Do give a try yourself first!
Click to view
while(q--)
{
flag=0;
cin>>d>>k;
//We can now check in logN time if the current degree is inside the set.
flag=degreeAtDistance[d].find(k)!=degreeAtDistance[d].end();//If the element is absent, then
//function returns degreeAtDistance.end()
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
SOLUTION:
The solutions are pasted in tabs below in case links dont work. This is only for your convenience so you dont have to wait for @admin to fix the links
Click to view
#include<bits/stdc++.h>
using namespace std;
#define NMAX 100005
vector<int> g[NMAX];
vector<int> d;
int main(){
//taking input
int n, m, q; cin>>n>>m>>q;
for(int i = 0; i < m; i++){
int u, v; cin>>u>>v; u--, v--;
g[u].push_back(v); g[v].push_back(u);
}
d = vector<int>(n, -1); d[0] = 0; // this array will contatin the distances from the capital city
//starting bfs from capital city = 0
queue<int> que; que.push(0);
while(!que.empty()){
int cur = que.front(); que.pop();
for(auto child : g[cur]){
if(d[child] != -1) continue;
d[child] = d[cur] + 1;
que.push(child);
}
}
set<pair<int, int> > nodes; // the set will contain, pair values in the form {distance, degree}
for(int i = 0; i < n; i++){
nodes.insert({d[i], g[i].size()});
}
//read the queries and answer them using the information in the set
for(int i = 0; i < q; i++){
int d, k; cin>>d>>k;
if(nodes.find({d, k}) != nodes.end()){
cout<<"YES"<<endl;
}else cout<<"NO"<<endl;
}
}
Click to view
/*
*
********************************************************************************************
* AUTHOR : Vijju123 *
* Language: C++14 *
* Purpose: - *
* IDE used: Codechef IDE. *
********************************************************************************************
*
Comments will be included in practice problems if it helps ^^
*/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int> arr[100100];
int visited[100100];
set<int> degreeAtDistance[100100];
//We make a custom data type below for convenience. It will store city number, and the distance from city 1.
struct node{
int city;
int distance;
};
int main() {
// your code goes here
#ifdef JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>m>>q;
int i,d,k,u,v;
for(i=0;i<m;i++)
{
cin>>u>>v;
arr[u].push_back(v);
arr[v].push_back(u);
}
//Input done.
queue<node> que;
node temp,b;
temp.city=1;
temp.distance=0;
que.push(temp);
visited[1]=1;
//Below is standard BFS algo. Note that BFS must be used for shortest path.
while(!que.empty())
{
temp=que.front();
que.pop();
u=temp.city;
degreeAtDistance[temp.distance].insert(arr[u].size());//Insert the degree of current node at
//distance =temp.distance
for(i=0;i<arr[u].size();i++)
{
if(!visited[arr[u][i]])
{
visited[arr[u][i]]=1;
b.city=arr[u][i];
b.distance=temp.distance+1;
que.push(b);
}
}
}
int flag=0;
while(q--)
{
flag=0;
cin>>d>>k;
//We can now check in logN time if the current degree is inside the set.
flag=degreeAtDistance[d].find(k)!=degreeAtDistance[d].end();//If the element is absent, then
//function returns degreeAtDistance.end()
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}
Time Complexity= O( \underbrace{N+M} _ {\text{BFS}}+\underbrace{Nlog_2N} _ {\text{Set insertion}}+\underbrace{QLog_2N} _ {\text{Answering queries}}) \equiv O((Q+N)log_2N) (as answering queries and making the set are most expensive part of computation in this question)
CHEF VIJJU’S CORNER 
1. Why DFS will give a wrong answer.
Click to view
Lets assume the simplest test case. Say, we have four nodes, connected like a square. Assume cuclic connection, i.e. 1 is connected to 2, 2 is connected to 3, 3 to 4 and 4 back to 1. Now, there are two paths from 1 to 2. One is directly 1\implies 2, the other is 1 \implies 4 \implies 3 \implies 2. DFS can go to any of the two paths! BFS, however, guarantees to visit all neighbours of 1 first, before starting any neighbor-of-neighbor-of-1. This difference marks the correctness of BFS, and incorrectness of DFS in given scenario.
2. As an exercise, try to make a small test case where BFS passes and DFS fails. The analysis and insight is always helpful, especially for debugging!
