PROBLEM LINK:Setter Adhyyan Sekhsaria DIFFICULTY:EASY PREREQUISITES:BFS on a Graph, Preprocessing, 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. QUICKEXPLANATION: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
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 selfpractice :) 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
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 prerequisites 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 "levelwise". 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 $k1$ 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 levelwise traversal, AND all edges are equiweighted (i.e. have same weight), we can see that it uses the "currently cheapest edge" to travel to an unvisited 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 datastructure 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  Now, why set?
A implementation of modified BFS to preprocess data/store answers is given below. Try to have an attempt yourself first though! An example function to answer queries using above ideas is given below. Do give a try yourself first! 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 :) $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 :D1. Why DFS will give a wrong answer. 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!
This question is marked "community wiki".
asked 03 Jul '18, 23:07

I used map of pairs,int to store distance and degree of each node and for each query i will just check whether that particular pair is set or not. So, the time complexity for my solution should be O(N+Q). correct me if i m wrong. answered 21 Jul '18, 01:28
Please give link to your solution. Also note that, if you used HashMap/unordered map, then its possible (although very difficult) to generate a worst case of $O(Q*N)$ for your solution if you use in built hashing function.
(21 Jul '18, 01:35)
I used simple map in c++ Here is my solution: https://www.codechef.com/viewsolution/19285092
(21 Jul '18, 01:45)
map has a complexity of $O(logN)$ for these operations. Your complexity is same as in editorial :)
(21 Jul '18, 01:47)
Thank you for the correction.
(21 Jul '18, 01:54)

Can somebody look into my code and tell me what's wrong. I am getting WA in 4th and 5th sub task. I am first finding the distance of each city from capital and then finding degree of each city. answered 27 Aug '18, 19:53

@vijju123 the time complexity seems wrong. Breadthfirst search runs in $\mathcal {O}(N+M)$, and for each node that was in the queue, we're inserting something into the set, which is $\mathcal{O}(\log_2N)$. Also, since the graph is connected, each node will be there in the queue exactly once. For $N$ nodes, the time complexity of the set operations will be $\mathcal{O}(N\log_2N)$. So, the overall time complexity comes out to be $\mathcal{O}(M+(N+Q)\log_2N)$. Please correct it in the editorial. answered 28 Nov '18, 15:28
Why is there a $(N+Q)Log_2N$ term in your complexity? We have $N$ things in set and searching them takes $log_2N$ per item, hence $QLog_2N$. Regarding $M$ term, it doesnt really matters in my opinion. We know that in worst case $M \equiv N$ hence $N+M \equiv 2*N \equiv O(N)$. But yes, using $M$ there is semantically correct.
(28 Nov '18, 16:36)
$Q\log_2N$ is for searching in the set $Q$ times, but $N\log_2N$ is for inserting degrees into the set $N$ times (for each of the $N$ nodes), which you're doing in this line: degreeAtDistance[temp.distance].insert(arr[u].size());Regarding $M$, in the worst case, $M$ will be equal to $\frac{N(N1)}{2} \approx N^2$, if there's an edge between every two nodes.
(28 Nov '18, 19:07)
Ah! You're being theoritical. Its good :).
$M \le 10^5$ in the question, hence my assumption/approximation. The reason why I did not go too much into deriving the time complexity was because its an easy problem, editorial is for beginners. They might get overwhelmed if I derive complexity of each and every stuff here. Hence I just give an easy, approximate complexity seeing which they get an idea that
(28 Nov '18, 22:07)
I will change it if you still feel the need though :)
(28 Nov '18, 22:09)
Thanks, though you have changed the complexity to what you had originally written. _
(29 Nov '18, 00:11)
Regarding $M$, even if $N \approx M$, I think it should still be mentioned in the time complexity, because not doing so would mean that, no matter what the size of the input is, the running time does not depend on the number of edges at all, which is wrong.
I wish editorialists on codeforces understood this (no sarcasm here). Sometimes, reading through the editorials on codeforces, it seems that they are only meant to explain the solution to higher rated coders/experienced people/people who could solve that particular problem.
(29 Nov '18, 00:18)
There, fixed for you. For CF, I will say it depends a lot on community. There are many red/highratedcoders coders there who want crisp editorials over everything and CF tends to it.
(29 Nov '18, 17:59)
showing 5 of 7
show all

A implementation of modified DFS to preprocess data/store answers is given below. Try to have an attempt yourself first though! It should be BFS ??
I was just checking your attention. ;). Even the setters missed that :p