2022-03-26：给定一个无向图，从任何一个点x出发，比如有一条路径: x -> a -> b -> c -> y

package main

import "fmt"

func main() {
  graph := [][]int{
    {1, 2, 3, 4, 5},
    {0, 2, 3, 4, 5},
    {0, 1, 3, 4, 5},
    {0, 1, 2, 4, 5},
    {0, 1, 2, 3, 5},
    {0, 1, 2, 3, 4}}
  ret := validPathSets(graph)
  fmt.Println(ret)
}

func validPathSets(graph [][]int) int {
  n := len(graph)
  // 任何一个合法路径的集合，都被弄成了整数形式
  // 0010010011 -> int
  // 甲 ：0011010011
  // 乙 ：0011010011
  // 丙 ：0011010011
  set := make(map[int]struct{})
  // 下面的过程：从每个点出发，0、1、2、3、。。。
  // 从x点出发，往外最多迈5步，所产生的所有路径，都要！
  for from := 0; from < n; from++ {
    dfs(0, 0, from, graph, set)
  }
  return len(set)
}

// int status -> 已经走过了哪些点的集合 ->  00001101
// int len -> 已经往外几步了！
// int cur -> 当前来到的是几号点！
// int[][] graph -> 图
// HashSet<Integer> set -> 收集所有合法路径的点集合！
func dfs(status, len, cur int, graph [][]int, set map[int]struct{}) {
  if (status & (1 << cur)) == 0 { // 之前走过的点，不包括cur，迈上去！
    len++
    status |= 1 << cur
    if len == 5 {
      set[status] = struct{}{}
    } else {
      for _, next := range graph[cur] {
        dfs(status, len, next, graph, set)
      }
    }
  }
}