代码随想录算法训练营第四十三天 | 98. 所有可达路径

邻接矩阵easy

package main import ( "fmt" ) var res [][]int var path []int func dfs(graph [][]int, x, n int) { if x == n { tmp := make([]int, len(path)) copy(tmp, path) res = append(res, tmp) return } for i := 1; i <= n; i++ { if graph[x][i] == 1 { path = append(path, i) dfs(graph, i, n) path = path[:len(path)-1] } } } func main() { var n, m int fmt.Scanf("%d %d", &n, &m) graph := make([][]int, n+1) for i := range graph { graph[i] = make([]int, n+1) } for i := 0; i < m; i++ { var s, t int fmt.Scanf("%d %d", &s, &t) graph[s][t] = 1 } path = append(path, 1) dfs(graph, 1, n) if len(res) == 0 { fmt.Println(-1) } else { for _, pa := range res { for i := 0; i < len(pa)-1; i++ { fmt.Print(pa[i], " ") } fmt.Println(pa[len(pa)-1]) } } }

邻接表easy

package main import ( "fmt" ) var res [][]int var path []int func dfs(graph [][]int, x, n int) { if x == n { tmp := make([]int, len(path)) copy(tmp, path) res = append(res, tmp) return } for _, i := range graph[x] { path = append(path, i) dfs(graph, i, n) path = path[:len(path)-1] } } func main() { var n, m int fmt.Scanf("%d %d", &n, &m) graph := make([][]int, n+1) for i := 0; i < m; i++ { var s, t int fmt.Scanf("%d %d", &s, &t) graph[s] = append(graph[s], t) } path = append(path, 1) dfs(graph, 1, n) if len(res) == 0 { fmt.Println(-1) } else { for _, pa := range res { for i := 0; i < len(pa)-1; i++ { fmt.Print(pa[i], " ") } fmt.Println(pa[len(pa)-1]) } } }