图论 | 98. 所有可达路径
98. 所有可达路径
题目链接： 98. 所有可达路径
思路
- 先创建邻接矩阵，再深搜
- 写代码是需要注意的是acm格式，输入的格式要转化为int，输出要转化为str，用map（）实现。
dfs
def dfs(grid,node,n,path,res):
if node == n:
res.append(path[:])
return
for j in range(len(grid[0])):
if grid[node-1][j] == 1:
path.append(j+1)
dfs(grid,j+1,n,path,res)
path.pop()
def main():
# 构造邻接矩阵
n,m = map(int,input().split())
grid = [[0]*n for _ in range(n)]
for _ in range(m):
node1,node2 = map(int,input().split())
grid[node1-1][node2-1] = 1
res = []
dfs(grid,1,n,[1],res)
if not res:
print(-1)
else:
for path in res:
print(' '.join(map(str,path)))
if __name__ == "__main__":
main()