CODEWITHSUNDEEP
algorithm
dejavu
dejavu

Reputation: 3254

Number of Crossings in bipartite graph

In a bipartite graph, there are n nodes on the left and m nodes on the right. Nodes are ordered from 1 to n and 1 to m. A node on the left is connected to the node on the right. All the nodes are not connected. For eg:

1 is connected to 4

2 is connected to 3

3 is connected to 2

3 is connected to 1

I want to know how many crossings are there in the graph( Here 5 crossings) . A similar problem is there on SPOJ

I want to know how this problem can be solved by using a Binary Index Tree as some users have mentioned. I am solving with O(n^2) algo and getting TLE.

This is not a homework. Yesterday I learned BIT and was searching for some problems so I came across this. Just tell me the trick. Please don't write the whole program.

Upvotes: 4

Views: 2046

Answers (2)

Evgeny Kluev
Evgeny Kluev

Reputation: 24667

Sort edges by the index of left node, then (for equal left indexes) by the index of right node. Look at indexes of right nodes. Each crossing in the graph corresponds to a pair of indexes going not in order in this sorted list. You need just to count such "not-in-order" pairs.

Sequentially insert each index of right node from sorted list into Binary Index Tree. After each insertion, you can find how many larger indexes are already in the tree in O(log(m)) time. So time complexity of the whole algorithm is O(h * (log(h) + log(m))): O(h * log(h)) for sorting and O(h * log(m)) to compute the number of index inversions (here 'h' is the number of edges). You can improve this to O(h * log(m)) using radix sort or bucket sort.

Update:

As noticed by Android Decoded, the number of inversions problem can be solved using a divide-and-conquer algorithm, based on Merge Sort. See detailed explanation here. This approach has larger time complexity O(h * log(h)) than the complexity of using a Binary Index Tree O(h * log(m)), but for sparse graphs, where number of edges is not much larger than number of nodes, it should be faster because it needs less memory and is more cache-friendly.

Merge Sort approach complexity may be improved to O(h * log(m)) if we eliminate duplicate entries during merge. To do so, apply Merge Sort to pairs of (value, numberOfInstances), where adjacent identical values are combined into one entry with proper 'numberOfInstances'. In worst case, no duplicates are eliminated for the first log(m) merge passes, this has the complexity of O(h * log(m)); then up to log(n) passes remain when duplicates are quickly eliminated in O(h) time.

Binary Index Tree usage details:

Implement a Binary Index Tree, that for given key can return its index in the tree, starting from the largest value (largest one -> index 0, second largest -> index 1, ...). Then after inserting each element into the tree, request its index - that would be the number of larger values standing to the left of this element in sorted list.

More details: Binary Index Tree may be implemented as a search tree, each node of which is augmented by the counter of descendant nodes. Don't create separate nodes for duplicate elements, just update descendant node counters for each of them. When asked for the index for some key, we should first search a node, corresponding to this index in the tree; then we should sum all the counters for immediate right descendant of every ancestor of current node, including right descendant of current node itself, but excluding all cases when current node is to the right of some of its ancestors.

Upvotes: 5

Imposter
Imposter

Reputation: 2686

If i have understood your question correctly then

we know we can have NpowerM(let this value be X) relations between two sets if we can find set which has no intersections(lets say we found it as Y) then we subtract the Y from X that is X-Y will be answer to your question mathematically.. inorder to find the Y you sort the elements on the other side say on set M and then find the longest increasing subsequence("http://en.wikipedia.org/wiki/Longest_increasing_subsequence") of N and M this can be done in O(nm) if your are clever enough then u can do it in O(NlogM) ... time . for clarity on solution (a similar problem exists here "http://people.csail.mit.edu/bdean/6.046/dp/" click building bridges link)

Upvotes: 0

Related Questions