给定一个无向图,
从任何一个点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)
}
}
}
}