DECUNI- Editorial

PROBLEM LINK:

Contest
Practice

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 :slight_smile:

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 :slight_smile:

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 :slight_smile:

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.size());//Insert the degree of current node at
	    //distance =temp.distance
	    for(i=0;i<arr.size();i++)
	    {
	        if(!visited[arr*])
	        {
	            visited[arr*]=1;
	            b.city=arr*;
	            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 :slight_smile:

Setter

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.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*, g*.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;
	}
}

Editorialist

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.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.size());//Insert the degree of current node at
	    //distance =temp.distance
	    for(i=0;i<arr.size();i++)
	    {
	        if(!visited[arr*])
	        {
	            visited[arr*]=1;
	            b.city=arr*;
	            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} _ { ext{BFS}}+\underbrace{Nlog_2N} _ { ext{Set insertion}}+\underbrace{QLog_2N} _ { ext{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 :smiley:

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!

6 Likes

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.

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.

http://dpaste.com/1EM3SEP

@vijju123 the time complexity seems wrong. Breadth-first 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.

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.

I used simple map in c++

Here is my solution: https://www.codechef.com/viewsolution/19285092

map has a complexity of O(logN) for these operations. Your complexity is same as in editorial :slight_smile:

Thank you for the correction.

A implementation of modified DFS to pre-process 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 :stuck_out_tongue:

1 Like

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.

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.size());

Regarding M, in the worst case, M will be equal to \frac{N(N-1)}{2} \approx N^2, if there’s an edge between every two nodes.

Ah! You’re being theoritical. Its good :).

Regarding M, in the worst case

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 Ok, complexities of these types are accepted for such problems.. for harder problems though, its fun deriving them :slight_smile:

I will change it if you still feel the need though :slight_smile:

Thanks, though you have changed the complexity to what you had originally written. -_-

This is the correct time complexity: \mathcal{O}(M+(N+Q)\log_2N)

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.

editorial is for beginners.

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.

There, fixed for you.

For CF, I will say it depends a lot on community. There are many red/high-rated-coders coders there who want crisp editorials over everything and CF tends to it.

I am not able to see your code.
I also got same wrong answer in first attempt. I stored all pairs of (D and degree) but missed to store source node i.e (1,Degree(1)).