nhudinhtuan

class TrieNode(object):

    def __init__(self):
        self.children = {}
        self.is_word = False    # mark the end of a word


class Trie(object):

    def __init__(self):

nhudinhtuan

from collections import deque

# graph: List[List[int]]
# s: start vertex
def bfs(graph, s):
    # set is used to mark visited vertices
    visited = set()

    # create a queue for BFS 
    queue = deque()

nhudinhtuan

# graph is represented by adjacency list: List[List[int]]
# s: start vertex
def dfs(graph, s):
    # set is used to mark visited vertices
    visited = set()

    def recur(current_vertex):
        print(current_vertex)

        # mark it visited

nhudinhtuan

# graph is represented by adjacency list: List[List[int]]
# s: start vertex
def dfs_iterating(graph, s):
    # set is used to mark visited vertices
    visited = set()

    # create a stack for DFS
    stack = []

    # Push vertex s to the stack

nhudinhtuan

# graph is represented by adjacency list: List[List[int]]
# DFS to detect cyclic
def is_cyclic_directed_graph(graph):
    # set is used to mark visited vertices
    visited = set()
    # set is used to keep track the ancestor vertices in recursive stack.
    ancestors = set()

    def is_cyclic_recur(current_vertex):
        # mark it visited

nhudinhtuan

# graph is represented by adjacency list: List[List[int]]
# DFS to detect cyclic
def is_cyclic_undirected_graph(graph):
    # set is used to mark visited vertices
    visited = set()

    def is_cyclic_recur(current_vertex, parent):
        # mark it visited
        visited.add(current_vertex)

nhudinhtuan

from collections import deque

class Solution(object):
    def orangesRotting(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        # corner cases

nhudinhtuan

# graph is represented by adjacency list: List[List[int]]
# using DFS to find the topological sorting
def topological_sort(graph):
    # using a stack to keep topological sorting
    stack = []

    # set is used to mark visited vertices
    visited = set()

    def recur(current_vertex):

nhudinhtuan

from collections import deque
# graph is represented by adjacency list: List[List[int]]
# s: start vertex
# d: destination vertex
# based on BFS
def find_shortest_path(graph, s, d):
    # pred[i] stores predecessor of i in the path
    pred = [-1] * len(graph)
    # set is used to mark visited vertices
    visited = set()

nhudinhtuan

import heapq
# graph is represented by adjacency list: List[List[pair]]
# s is the source vertex
def dijkstra(graph, s):
    # set is used to mark finalized vertices
    visited = set()
    # an array to keep the distance from s to this vertex.
    # initialize all distances as infinite, except s
    dist = [float('inf')] * len(graph)
    dist[s] = 0