Problem link : contest practice
Difficulty : Medium
Pre-requisites : Graph, Bitmasking, BFS
Problem :
You have a unweighted directed graph G of at max N vertices. You are given the adjacency matrix in input. There are Q phases of queries. In each phase you are given M queries of form Li,Ri. For each query if there is already existing an edge from Li to Ri, you have to remove it, else you have to add it. For each phase after M queries you are given a V, you have to print sum of distances of all reachable nodes from V. Sum of M over all phases <= 250000.
Explanation
We can find sum of distances of all reachable nodes from a certain node V using BFS since edges are unweighted. You can learn simple BFS algorithm from internet(wide resources are available).
How to get 20/50 points
If you are using Floyd-Warshall or slower algorithms to find shortest path you will get 20 points only.
If you are using adjaceny matrix you can updated edges in O(1) and a bfs will take O(NN), leading to a total complexity of O(NN*Q + sum(M)) using which you can get 20/50 points.
If we use adjacency lists we can do BFS in O(N) but updating edges will not be O(1). So complexity will be O(N*Q + sum(M)*K) where O(K) is the complexity of removing/adding element to a list of N elements. Using this you can get 50 points.
How to get 100 points
The idea is to store every 32 bits of the adjacent matrix in an unsigned int. Since 32 is sqrt(1024), so it takes O(n*sqrt(n)) for each BFS we do and O(1) for each arc modification.
Detailed explanation:
For each node i we store an array of 32 unsigned int. Each unsigned int has 32 bits. So for each node we have a total of 32*32 bits available. Say, we have b_1,b_2,b_3…b_n, where b_j is set if there is an edge from current node to node j.
While doing BFS, we maintain a visited list. We need to find adjacent neighbours of a certain node v that have not been visited yet. For this we take AND of bitmask of adjacant neighbours of vertex v and !(visited list). This will give you list of vertices you need to visit next. But now you need to support the following operation fastly:
finding out the first non-zero bit in a bitmask. For that we can traverse over each unsigned int until we find a positive integer: means the first set bit is present in that integer (most significant bit). We will need to find the first non-zero bit in an unsigned int. Please see the Find_first_set link for understanding how this function can be implemented in various languages.
So, we need two operations:
1.) Flip the j’th bit of bitset ie. set or unset b_j. We can find the respective unsigned int in which j’th bit is present and flip the respective bit. This is done in O(1).
2.) Get the neighbours of node i. So in the bitset of i, we search for bits which are set 1. We can do this traversing over the whole bitset and finding which bits are set. This can be optimised because we don’t have to check the whole array, we can just check one unsigned int’s value to find if there is a neighbour in the cluster denoted by it.
So, we can now do a simple BFS using above utilities. Since, we have divided the adjacency matrix into N/32 partitions for each vertex: total complexity total will be O((NNQ)/32 + sum(M)).