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.