How can we calculate number of node — disjoint paths pair between u and other vertex say v (such that distance of v from source vertex is K).Vertex v is not known to us. I thought of implementing BFS for every node until maximum distance from source node is <= K. But I am not getting idea for implementation. Anybody please help me? Given the number of vertices in graph can be up to than 10^5 and edges can be 6 * 10^5. In every test case, value of K will be at max 10 % of number of edges.
A path is sequence of vertices: s, v_1, .., v_m, t. Two paths s, v_1, .., v_m, t and s, u_1, ..., u_k, t are called node-disjoint if v_i != u_j for any valid i and j.
We are given a example graph shown as following. Adjacency List representation of given Directed Graph
1 - 2, 5
2 - 3, 4, 6
3 - 4
4 - 8
5 - 7
6 - 11
7 - 11
8 - 9, 10
9 - 10
10 - 11
Value of K is 6(including source node and end node).
Total node — disjoint path pairs possible are 3(between 1 and 11) + 1(between 2 and 4) + 1(between 8 and 10). In case of path of 1 to 11
Path 1: 1 - 6 - 11
Path 2: 1 - 2 - 4 - 8 - 10 - 11
Path 3: 1 - 5 - 7 - 11
Total combinations = Comb(3, 2) = 3
Anybody please help me out with implementation using BFS or DFS of above question. Can this question be solved using DP + DFS or DP + BFS?
UPD : In every test case, value of K will be at max 10 % of number of edges.