Bridge and Query

Recommended to know before  proceeding further

• Concept of bridge and Bridge Tree in a graph.
• LCA (Lowest Common Ancestor) of n -array tree (Dynamic Programming)
   

The idea is to first build a “Bridge Tree” and then handle the query using this “Bridge Tree”.

Let’s say for the given query ‘A’, ‘B’, ‘C’ and ’D’.The Node ‘A’ lies in component ‘Ca’ of the “Bridge tree”. Similarly, node ‘B’ lies in  'Cb’, ‘C’ lies in  ‘Cc’ and ‘D’ lies in ‘Cd’ component of “Bridge Tree”.
 

After adding nodes ‘A’ and ‘B’ in the graph, all bridges from ‘Ca’ to ‘Cb’ in the bridge tree are destroyed ( property of bridge tree). So, our answer would be the distance between components of  ‘C’ and ‘D’ (‘Cc’ and ‘Cd’ ) in the tree minus the edges which occur on the path from ‘Ca’ to ‘Cb’ (ie. a number of edges in the intersection of paths Ca' - ‘Cb’ and ‘Cc’ - ‘Cd’).

Now, we just have to find the length of intersection of paths ‘A' - ‘B’ and ‘C’ - ‘D’. components Let's break down each path into two parts because finding intersections between straight chains would be easier. So, let  u = LCA(A, B)  and  v = LCA(C, D) , so total intersection would be intersection(u, a, v, c) + intersection(u, a, v, d) + intersection(u, b, v, c) + intersection(u, b, v, d).

Note, the above ‘A’, ‘B’, ‘C’ and ‘D’ are components of given nodes respectively.
 

To find the distance between two nodes in a tree we will use the formula, D( A, B) = Distance of node ‘A’ from root + Distance of node ‘B’ from the root - 2 *  distance of node LCA(A, B) from the root,  where distances from root to all nodes can be calculated using a DFS and for calculating LCA we can use Dynamic Programming.
 

Algorithm :

Consider the following global variables

• Array of integer list, ‘graph’ to store graph
• Array ‘U’ and ‘V’ to store the edge
• Array ‘isBridge’, to check whether ‘i-th’ edge is bridge or not
• Array of integer list, ‘graph’ to store bridge tree
• Array ‘visited’, to check whether ‘i-th’ node is visited or not
• Array ‘parent’, to store the parent of each node
• Variable ‘timer’, to give discovery time of each node
• Array ‘disc’ to store the discovery time of each node
• Variable ‘component’, to give the component-time of each node
• Array  ‘L’ to store the ancestor of ‘i-th’ node
• 2D array P[][] to store the LCA
• Array ‘C’ to store the component
• Array ‘start’ and  ‘finish’  to store the discovery and discovered time of each node in the bridge tree.

Let ‘countBridge(n, m, q, edges, operation) ’ be the function to count the number of bridges between edge ‘C’ and ‘D’ after adding edge ‘A’ and ‘B’.
 

• Run a loop from 0 to m to construct graph using given edges
  • Let ‘u’ = edges[i][0] and ‘v’ = edges[i][1]
  • Decrement  ‘u’ and ‘v’  by 1.
  • Push back ‘i’ in graph[‘v’]
  • Push back ‘i’ in graph[‘u’]
• Initialize visited array with 0
• Make function dfs0(start, parent)
• Call function dfs0(0, -1),
• Make function dfs1(start) , to construct a bridge tree.
• Call function dfs1(0)
• Make function dfs2(start, parent), to fill P[][] array ( for finding LCA )
• Call function  dfs(0, -1)
• Take an array ‘ans’ to store the answer to the ‘q’ query.
• Run a loop from 0 to q
  • Let ‘a’ = operation[i][0], ‘b’ = operation[i][1], ‘c’ = operation[i][2] and ‘d’ = operation[i][3].
  • Decrement ‘a’, ‘b’, ‘c’ and ‘d’ by 1.
  • Take a temporary variable ‘temp’ and store the return ans of countBridge(component[‘a’],  component[‘b’],  component[‘c’],  component[‘d’])

Description of dfs( start(u), parent(p)) function:

This function finds the discovery time of each node in the given graph, also it marks the ‘isBridge’ array if the edge between U[i] - V[i] is a bridge. This function returns the ‘low’ value of node ‘u’.
 

• Mark ‘visited[u]’ true
• Increment ‘timer’ by 1.
• Store ‘timer’ is ‘disc[u]’
• Take a variable ‘low’ , initialize it to ‘timer’
• Run a loop from 0 to the size of graph[u], to visit all adjacent vertices
  • Take a variable ‘adj’ initialize it to graph[u][i]
  • Make a function ‘adjacent( ‘u’, adj)’ that returns the node adjacent to ‘u’ and edge numbered ‘adj’
  • call function ‘adjacent(u, adj)’ and store the return value in variable ‘v’.
  • If ‘visited[‘v’] is equal to 0
    • Call recursively dfs0(‘v’, ‘adj’) and store the return value in ‘mn’.
    • Update ‘low’ with a minimum of ‘mn’ and ‘low’.
    • If ‘disc[u]’ is less than ‘mn’
      • Mark ‘isBridge[adj]’ equal to 1.
  • Else if ‘adj’ is not equal to parent ‘p’
    • Update ‘low’ with a minimum of  ‘disc[v]’ and ‘low’.
• Return ‘low’.

Description of ‘adjacent(node(u), edgeNumber(adj))’   function:
 

• If U[‘adj’] == ‘u’
  • Return V[‘adj’]
• Else
  • Return U[‘adj’]

Description of dfs1(node(s)) function:

This function is used to construct a bridge tree.

• Push ‘s’ in ‘Queue[component]
• Mark ‘visited’[s]’ equal to 1.
• Take a variable ‘currComponent’ initialize it to ‘component’
• While Queue[currComponent] is not empty
  • Take a variable ‘node’ initialize it with the front element of Queue[currComponent]
  • Pop front from ‘Queue[currComponent]’
  • Store ‘currComponent’ at  ‘componentNo[node]’
  • Run a loop from 0 to size of ‘graph[node]’
    • Take a variable ‘adj’ and store the value graph[node][i]
    • Take a variable ‘v’ and store the return value of adjacent(node, adj)
    • If edge ‘adj’ is a bridge and ‘visited[v] is false
      • Increment the ‘component’ number
      • Push back ‘component’ in ‘Tree[currComponent]
      • Push back ‘currComponent’ in ‘Tree[‘component’]
      • Recursively call ‘dfs1(‘v’)
    • Else if visited[‘v’] is false
      • Mark visited[‘v’] true
      • Push back ‘v’ in ‘Queue[currComponent].

Description of dfs2(node(u), parent(p)) function:

• If ‘p’ is not equal to -1, make L[u] equal to L[p] + 1, otherwise 1.
• Store ‘p’ in p[0][u]
• Increment ‘now’ by 1
• Initialize ‘start[u]’ with ‘now’
• Run a loop from 1 to ‘MAXL’
  • Take a variable ‘x’ initialize it with P[j - 1][u]
  • If ‘x’ is less than 0
    • Break
  • Else
    • Store P[j - 1][x] in P[j][u]
• Increment ‘vis’ by one
• Run a loop from 0 to the size of ‘Tree[u]’
  • Take a variable ‘v’ initialize it with ‘Tree[u][i]
  • If ‘v’ is equal to ‘p’ continue the loop
  • Else recursively call dfs2( v, u)
• Increment ‘now’ by 1
• Store ‘now’ in ‘finish[u]’
• Return

Description of ‘countBridge(a, b, c, d)’ function:

• Make function ‘lca(u, v)’, that returns the lowest common ancestor of node ‘u’’ and ‘v’
• Call function lca(a, b) and store the return value in variable ‘u’
• Call function lca(c, d) and store the return value in variable ‘v’,
• Make function ‘getdist(c, d, v) , that return the distance between node ‘c’  and node ‘d’ with the help of lca ‘v’,
• Call function ‘getdist(c, d, v)’ and store the return value in variable ‘ret’.
• Take a variable ‘X’
• Make function getCommonPath(u, a, v, c), it returns the common path between path ‘u’ to ‘a’ and path ‘v’ to ‘c’
• Call function getCommonPath(u, a, v, c) and store the return value in ‘X’
• Call function getdist(X.first, X.second, lca(X.first,X.second)) store the return value in variable ‘temp’
• Subtract ‘temp’ from ‘ret’.
• Call function getCommonPath(u, a, v, d) and store the return value in ‘X’
• Call function getdist(X.first, X.second, lca(X.first,X.second)) store the return value in variable ‘temp’
• Subtract ‘temp’ from ‘ret’.
• Call function getCommonPath(u, b, v, c) and store the return value in ‘X’
• Call function getdist(X.first, X.second, lca(X.first,X.second)) store the return value in variable ‘temp’
• Subtract ‘temp’ from ‘ret’.
• Call function getCommonPath(u, b, v, d) and store the return value in ‘X’
• Call function getdist(X.first, X.second, lca(X.first,X.second)) store the return value in variable ‘temp’
• Subtract ‘temp’ from ‘ret’.
• Return ‘ret’
•  

Description of lca(p, q) function:

This function returns the LCA of node ‘p’ and ‘q’

• Take a variable ‘log’ and ‘i’
• If ‘L[p]’ is less than ‘L[q]’
  • Swap ‘p’ and ‘q’
• Initialize ‘log’ with 1 and run a loop from 1 to L[p] while 2 times of log is less than L[p]
  • Increment ‘log’ by 1.
• Run a loop from ‘i’ equal to ‘log’ to 0 , decrementing ‘i’ in each step
  • if (L[p] - (1 << i) is greater than equal to  L[q])
    • Store P[i][p] in ‘p’.
• If p is equal to ‘q’
  • Return ‘p’
• Run a loop from ‘i’ equal to ‘log’ 0
  • if ‘P[i][p]’ is not equal to -1  and P[i][p]  is not equal to P[i][q])
    • Store ‘P[i][p]’ in ‘p’
    • Store ‘P[i][q]’ in ‘q’
• Return ‘P[0][p]’

Description of ‘getCommonPath( u, a, v, b)’ function:

This function returns a common path between path u -> a and v -> b.

• Make a function ‘isAncestor(v, a)’ , checks whether ‘v’ is the ancestor of ‘a’ or not
• If ‘isAncestor(v,a)i is true
  • return pair(0,0) because ‘v’ has to be an ancestor of ‘a’ to have any common path
• Else take a variable  ‘x’ and store the return value of  ‘lca(a, b)’
• If L[v] is less than L[u] , ‘ v’ is an ancestor of ‘u’, so the beginning of the common path should be from ‘u’
  • If ‘isAncestor(u,x)’ is true i.e  if ‘u’ is not an ancestor of ’x’  no common path exists
    • return pair(u ,x) i.e  u -> x is the common path
• Else,  ‘u’  is an ancestor of ‘v’, so the beginning of the common path should be from’ ‘v
  • If ‘isAncestor(v,x)’ is true, i.e  if ‘v’ is not an ancestor of ‘x’ no common path exists
    • return pair(v, x); i.e  v -> x is the common path
• return pair(0, 0)

Description of ‘isAncestor(u, a)’ function:

This function checks whether node ‘u’ is the ancestor of node ‘a’ or not. If yes then return true else return false.

• If ‘u’ is equal to ‘a’ return true
• If ‘start[u]’ is less than ‘start[a]’ and ‘finish[u]’ is greater than ‘finish[a]’
  • return true
• else
  • return false
  •  

Description of getdist(a, b, lca) function

This function returns the distance between node ‘a’ and node ‘b’ with the help of lca node.

• Return L[a] + L[b] - 2 * L[lca]

O((M + N) * logN)    where ‘N’ is the number of nodes ‘M’ is the number of edges

Every dfs function is O(M + N) and for each query, we are finding LCA that takes O(logN).

In the worst case, the number of queries is equal to the number of nodes ‘N. So the overall time complexity is O((M + N) log(N)).

O(M + N)    where ‘N’ is the number of nodes ‘M’ is the number of edges

Mainly we are using space in creating graphs and trees, which takes O(N + M) space.