Graph Path Count
EasyPractice library · +10 XPgraphsbfspaths
Given an undirected graph with N nodes and M edges, and two specific nodes, S and T, find the total number of distinct simple paths from node S to node T. A simple path is one that does not revisit any node. Nodes are numbered from 0 to N-1.
Input
The first line contains three integers N, M, S, and T, separated by spaces. The next M lines each contain two integers U and V, representing an edge between nodes U and V.
Output
Print a single integer, the total number of distinct simple paths from S to T.
Constraints
1 <= N <= 10; 0 <= M < N*(N-1)/2; 0 <= S, T, U, V < N; S != T.
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
4 4 0 3 0 1 0 2 1 3 2 3
Output
2
There are two simple paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
Example 2
Input
3 2 0 2 0 1 1 2
Output
1
There is one simple path: 0 -> 1 -> 2.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
4 4 0 3 0 1 0 2 1 3 2 3
Example 2 input
3 2 0 2 0 1 1 2