Count of simple paths starting from source node

Given an undirected graph with N nodes and M edges in the form of array edg[][2], the task is to count all simple paths (paths without repeated vertices) from source node 1 in the given graph.

Examples:

Input: N = 4, edg[][2] = {{1, 2}, {2, 3}}
Output: 3
Explanation:  

• path 1: 1
• path 2: 1 -> 2
• path 3: 1 -> 2 -> 3

Input: N = 4, edg[][2] = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3 4}}
Output:  16

Approach: To solve the problem follow the below idea:

The idea is to use recursion to traverse the graph starting from the source node and keep track of visited nodes and increment the counter for each path found. Traverse unvisited neighbors, and unmarks visited nodes so that multiple paths can be explored. Returns the total count of simple paths found.

Below are the steps for the above approach:

• Declare adjacency list adj[N + 1] and iterate on all M edges and fill adjacency list.
• Initialize a visited array of size N+1 with 0, vis[N + 1].
• Declare a variable say ans = 0.
• Create recursive function recur(), mark the current node visited and increment the ans by 1 and traverse its unvisited neighbors.
• When exiting the current node, unmark the node from the visited array.
• Return the variable ans.

Below is the implementation of the above approach:

Time Complexity: O(N!)  
Auxiliary Space: O(1)

Given an undirected graph with N nodes and M edges in the form of array edg[][2], the task is to count all simple paths (paths without repeated vertices) from source node 1 in the given graph.

Examples:

Input: N = 4, edg[][2] = {{1, 2}, {2, 3}}
Output: 3
Explanation:  

• path 1: 1
• path 2: 1 -> 2
• path 3: 1 -> 2 -> 3

Input: N = 4, edg[][2] = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3 4}}
Output:  16

Approach: To solve the problem follow the below idea:

The idea is to use recursion to traverse the graph starting from the source node and keep track of visited nodes and increment the counter for each path found. Traverse unvisited neighbors, and unmarks visited nodes so that multiple paths can be explored. Returns the total count of simple paths found.

Below are the steps for the above approach:

• Declare adjacency list adj[N + 1] and iterate on all M edges and fill adjacency list.
• Initialize a visited array of size N+1 with 0, vis[N + 1].
• Declare a variable say ans = 0.
• Create recursive function recur(), mark the current node visited and increment the ans by 1 and traverse its unvisited neighbors.
• When exiting the current node, unmark the node from the visited array.
• Return the variable ans.

Below is the implementation of the above approach:

Time Complexity: O(N!)  
Auxiliary Space: O(1)