all_paths_dag.py

# Enter your code here. Read input from STDIN. Print output to STDOUT
from collections import defaultdict
from copy import deepcopy

def get_adj_list_and_zero_degree(no_of_nodes, all_edges):
    all_node_nos = {i for i in range(no_of_nodes)}
    adj_mat = defaultdict(list)
    in_nodes = set()
    for e in all_edges:
        adj_mat[e[0]].append(e[1])
        in_nodes.add(e[1])
    zero_in_degree = all_node_nos - in_nodes
    return adj_mat, zero_in_degree

def get_all_paths(start_node, visited_list, current_path, all_path, adj_mat):
    visited_list[start_node] = True
    current_path.append(start_node)
    if adj_mat[start_node]:
        for ch in adj_mat[start_node]:
            if not visited_list[ch]:
                get_all_paths(ch, visited_list, current_path, all_path, adj_mat)
    else:
        all_path.append(deepcopy(current_path))
    current_path.pop()
    visited_list[start_node] = False

def main():
    n = int(input().split()[0])
    edges = list()
    while True:
        try:
            r = input()
            current_code = tuple(list(map(int,r.split(','))))
            edges.append(current_code)
        except Exception as e:
            break
    adj_mat, zero_degree_node = get_adj_list_and_zero_degree(n, edges)
    all_paths = list()
    current_path = list()
    visited_list = [False] * n
    # print(zero_degree_node)
    # print(visited_list)
    # print(adj_mat)
    for s in zero_degree_node:
        get_all_paths(s, visited_list, current_path, all_paths, adj_mat)
            
    for c_p in all_paths:
        print("->".join('{}'.format(c) for c in c_p))

if __name__ == '__main__':
    main()