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

2022-03-26：给定一个无向图， 从任何一个点x出发，比如有一条路径: x -> a -> b -> c -> y， 这条路径上有5个点并且5个点都不一样的话，我们说(x,a,b,c,y)是一条合法路径， 这条合法路径的代表，就是x,a,b,c,y所组成的集合，我们叫做代表集合， 如果从b到y，还有一条路径叫(b,a,c,x,y)，那么(x,a,b,c,y)和(b,a,c,x,y)是同一个代表集合。 返回这个无向图中所有合法路径的代表集合数量。 题目给定点的数量n <= 15，边的数量m <= 60， 所有的点编号都是从0~n-1的。 来自美团。

代码用golang编写。代码如下：

深度优先遍历。

执行结果如下：

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)
			}
		}
	}
}

执行结果如下：

左神java代码