Edges on a path

4.4

23 votes
Algorithms, Articulation Points and Bridges, Bridges, C++, Graphs
Problem

Given a connected graph with n nodes and m edges, where m <= n.You are also given two nodes a and b of the graph.
You need to find the number of edges which are present in all paths between a and b.

CONSTRAINTS:

1 <= N <= 105

N-1 <= M <= min(105,N)

1 <= a,b <= N possibly a = b.

INPUT FORMAT :

The First line contains two space separated integers N and M, the number of nodes and edges respectively.
The second line contains two space separated integers a and b.
Then m lines follow, the i-th line contains two integers xi and yi (1≤xi,yi≤n, xi≠yi) --- the endpoints of the i-th edge.

OUTPUT FORMAT :

The output should contain a single number which is the number of edges present in all paths between a and b.

Sample Input
5 5
2 5
1 3
3 5
3 4
2 3
1 2
Sample Output
1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The edge (3,5) lies in all paths between node 2 and 5. This is the only edge which occurs in every path between 2 and 5.

Therefore, the answer is 1.

Editor Image

?