Monday, May 29, 2017

A Connectivity Problem on Directed Graph

Rachit Jain, rachit iit roorkee, rachit iitr, rachit codechef, rachit hackerrank, rachit jain microsoft
Tags: bitsets, graphs, SCC, connectivity

So the Hackerrank Codesprint 11 ended, and here is the question that I will talk about today: you are given a directed graph, and you will be given 2 types of queries: introduce a new node with an edge from/to the existing nodes, or answer whether there is a path from node $x_i$ to node $y_i$.

If it were a undirected graph, DSU would have nailed it.
Anyway, this is a standard technique used for connectivity in directed graphs.
As for now, forget the type of query that modifies the graph structure.
1. Find all the SCCs in the directed graph.
2. Form a new graph, a DAG by compressing the SCCs and adding edges between the SCCs.
3. Now for each SCC $A$, maintain the list$(reach[A])$ of all the SCCs it can reach.
4. For given nodes $x$ and $y$, there is a path from $x$ to $y$ iff the SCC component $Y$ is present in $reach[X]$, where $X,Y$ refer to the SCC that contain $x,y$ respectively.

Note that this takes $O(n^2)$ because of step $3$. We can do it faster by using BITSETS. Click the above link which excellently outshows the applications of bitsets in C++.
So we replace the list $reach[A]$ by the bitset $bit[A]$.

So we now do this in $O(\frac{N^2}{32})$. This is pretty fast to pass the TL.

Now notice that queries modifying the structure of graph won't affect our algorithm much.
We first build the complete graph and then finally answer the queries.
The only thing that one can worry about is that there might be some case for which the answer to present query is "No" but since we have built the complete graph, we might get a "Yes".
So if answer for $x,y$ is "No", then this means that till now there isn't a path from $x$ to $y$. Notice that as we continue to modify the graph, we always bring a NEW node inside the structure and it's never possible in this way to add a path from $x$ to $y$.  Wow!

As usual, here is the code implementing the above idea.
I've seen similar questions in past hackerrank contest too(can't recall it).
So I learnt that using bitsets is a standard technique for connectivity queries on directed graphs.

5 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Can you please explain how the time complexity is getting reduced by using bitsets?

    ReplyDelete
    Replies
    1. Hi harsh, lets say you have 2 sets of 30 numbers each. What will you do if you want to make a set which is union of both of them? You can have an array mark, where mark[x] = 1 means you have x. So you iterate on 30 numbers in both sets, and mark those elements. With bitset, you just need to do set[c] = set[a] | set[b]. So bitset allows to reduce time complexity by a factor of 32, 64 depending on int, long long.

      Delete
    2. How to modify it when we have more then 32 components that we can reach?

      Delete

Cracking the Google Interview | Software Engineer reveals tips & secrets

rachit jain blog, Rachit Jain, rachit jain iit roorkee, rachit jain iitr, rachit iitr,rachit codechef, rachit hackerrank, rachit jain micr...