trailblazer995's blog

Difficult Graph Problem
By trailblazer995, history, 4 years ago, In English

Hi, I came across a problem in hackerrank test, the problem statement was:

Given an undirected graph with N nodes and M edges, each edge contains a gadget with id i (where 1 <= i <= G), after that you're given Q queries, in each query you've two nodes u and v, you've to find number of distinct gadgets in all simple paths from u to v. Constraints: 1 <= N, Q, M <= 10^5 1 <= G <= 40 Time Limit: 1 sec

I was unable to solve it and couldn't find a solution on internet as well, can anyone tell how to solve it or whether it's not possible solve it

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

If simple path means that you can't pass through an edge more than once then here's an approach:

Find the bridges in the graph and then make a tree where the edges are the bridges and the nodes are the cycles in the graph. Now for each edge in the graph it's either a bridge or not. If it is, then add one to the corresponding edge in the tree. If it's not, then add one to the node in the tree containing the edge.

now for each query $$$u,v$$$ find the corresponding nodes in the tree and the answer is the sum of values of all edges and nodes in the simple path between them. That's because once you pass an edge in the tree (Which is a bridge in the graph) you can't go back and each gadget on the simple path between them can be collected. You can find the answer using Lowest Common Ancestor on the tree.

Time complexity: $$$O(N log_2 N)$$$

I'll try to code it and send you the code when I'm done.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This solution seems fine, thanks for the help

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same solution but can we remove the LCA and change it by Euler tour with MO is that correct?

    → Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

One way is to find biconnected components and make a tree out of them. So like the components become vertices and the bridges in the original graph are edges. For every biconnected component you also need to calculate all the different gadgets on the edges in it. If we enter a component, we can get all the gadgets in it.

Now we have a tree, and the solution for a query is the union of all the gadgets in the biconnected components and the bridges on the simple path from the component of u to the component of v in the tree.

With G being so small, you can keep a bitmask of all the gadgets and use binary lifting solve every query in $$$O(log N)$$$.

Time complexity: $$$O(Q * log N)$$$, Memory: $$$O(N * log N)$$$.

For bigger G I think you should be able to do Mo's algorithm on the tree to get an ok complexity. I think the complexity in that case is: $$$O(Q * sqrt(N))$$$ but I'm not 100% sure on that.

→ Reply