<reponame>shinalone/alg<filename>alg/classic/dfs.py
# coding=utf-8
# author=uliontse

from typing import List


class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def _dfs(i, visited, n):
            visited[i] = 1
            for j in range(n):
                if not visited[j] and isConnected[i][j] == 1:
                    _dfs(j, visited, n)
            return

        n = len(isConnected)
        visited = [0] * n
        cnt = 0
        for i in range(n):
            if visited[i] == 0:
                _dfs(i, visited, n)
                cnt += 1
        return cnt


class Solution2:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def _dfs(graph, begin, end, paths, stack):
            if begin == end:
                paths.append(stack[:])
                return paths

            for v in graph[begin]:
                stack.append(v)
                _dfs(graph, v, end, paths, stack)
                stack.pop()
            return paths

        return _dfs(graph, 0, len(graph)-1, [], [0])


if __name__ == '__main__':
    graph = [[1,2],[3],[3],[]]
    print(Solution2().allPathsSourceTarget(graph))

# coding=utf-8
# author=uliontse

from typing import List


class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def _dfs(i, visited, n):
            visited[i] = 1
            for j in range(n):
                if not visited[j] and isConnected[i][j] == 1:
                    _dfs(j, visited, n)
            return

        n = len(isConnected)
        visited = [0] * n
        cnt = 0
        for i in range(n):
            if visited[i] == 0:
                _dfs(i, visited, n)
                cnt += 1
        return cnt


class Solution2:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        def _dfs(graph, begin, end, paths, stack):
            if begin == end:
                paths.append(stack[:])
                return paths

            for v in graph[begin]:
                stack.append(v)
                _dfs(graph, v, end, paths, stack)
                stack.pop()
            return paths

        return _dfs(graph, 0, len(graph)-1, [], [0])


if __name__ == '__main__':
    graph = [[1,2],[3],[3],[]]
    print(Solution2().allPathsSourceTarget(graph))
# coding=utf-8 # author=uliontse