admin管理员组文章数量:1312811
- Here's a link to the actual question.
- Here's a link to the full code on Go Playground, with some test cases that return the correct result
My code is correct, just slow it seems? I'm not a programmer by training, I'm a physicist by education and sysadmin by profession, with an interest in programming.
The problem, as I understand it, is that given a graph composed of connected subgraphs, find the sum of the maximum depths of the BFS tree for each component. My procedure for solving this is as follows.
- Find all the connected subgraphs using a Union Find
- For each subgraph, construct a BFS tree from each vertex and return the maximum depth possible. Ensure the graph is bipartite while computing the BFS tree.
The main logic is in this function, and everything this function depends on is written below. I construct an adjacency list backed graph from the list of edges, compute all the connected subgraphs using a Union-Find, and for each subgraph (represented as a list of vertices), run a BFS rooted at each vertex to find the deepest tree possible. Finally I return the sum of the depths of all deepest trees.
func magnificentSets(n int, edges [][]int) int {
// Construct graph
g := GraphWithCapacity(n)
set := DisjointSetWiithCapacity(n)
for _, e := range edges {
src := e[0] - 1
dst := e[1] - 1
if !g.AddEdge(src, dst) {
fmt.Printf("Unable to add edge {%d, %d}\n.", src, dst)
}
set.Union(src, dst)
}
connected_subgraphs := make(map[int][]int)
for n := range g.EachNode() {
p := set.Find(n)
connected_subgraphs[p] = append(connected_subgraphs[p], n)
}
total_maxdepths := 0
for _, vlist := range connected_subgraphs {
if len(vlist) == 1 {
total_maxdepths += 1
continue
}
maxdepth := 0
for _, v := range vlist {
_, depthatv, err := bfs(g, v)
if err != nil {
fmt.Println(err.Error())
return -1
}
if depthatv > maxdepth {
maxdepth = depthatv
}
}
total_maxdepths += maxdepth + 1
}
return total_maxdepths
}
Here's my code broken down and explained. I have a data structure for the union-find part, which consists of a factory to initialize with a given number of nodes, and the Union and Find functions on it.
type disjoint_set struct {
parent []int
}
func DisjointSetWiithCapacity(n int) disjoint_set {
parent := make([]int, n)
for idx := range parent {
parent[idx] = idx
}
return disjoint_set{parent}
}
func (uf *disjoint_set) Find(node int) int {
cnode := node
for uf.parent[cnode] != cnode {
cnode = uf.parent[cnode]
}
uf.parent[node] = cnode
return cnode
}
func (uf *disjoint_set) Union(node_1, node_2 int) bool {
p1 := uf.Find(node_1)
p2 := uf.Find(node_2)
if p1 == p2 {
return false
}
child := max(p1, p2)
parent := min(p1, p2)
uf.parent[child] = parent
return true
}
Then I have a graph data structure representing my graph as a full adjacency list.
type ErrNodeNotFound struct {
nodeid int
}
func (e ErrNodeNotFound) Error() string {
return fmt.Sprintf("Node %d not found in graph.\n", e.nodeid)
}
type graph struct {
fadjlist [][]int
}
func GraphWithCapacity(cap int) graph {
return graph{fadjlist: make([][]int, cap)}
}
I have methods on it to
- Add a node
- Add an edge
- Check if node exists
- Compute neighbors of a node
- Iterators over nodes and edges
func (g *graph) AddNode() int {
g.fadjlist = append(g.fadjlist, make([]int, 0))
return len(g.fadjlist) - 1
}
func (g *graph) HasNode(nodeid int) bool {
return nodeid < len(g.fadjlist)
}
func (g *graph) EachNode() iter.Seq[int] {
return func(yield func(int) bool) {
for i := 0; i < len(g.fadjlist); i += 1 {
if !yield(i) {
return
}
}
}
}
func (g *graph) EachEdge() iter.Seq2[int, int] {
return func(yield func(int, int) bool) {
for src, adjlist := range g.fadjlist {
for _, dst := range adjlist {
if dst > src {
continue
}
if !yield(src, dst) {
return
}
}
}
}
}
func (g *graph) AddEdge(from, to int) bool {
src := min(from, to)
dst := max(from, to)
if !g.HasNode(src) || !g.HasNode(dst) {
return false
}
if slices.Contains(g.fadjlist[src], dst) {
return false
}
g.fadjlist[src] = append(g.fadjlist[src], dst)
g.fadjlist[dst] = append(g.fadjlist[dst], src)
return true
}
func (g *graph) Neighbours(nodeid int) ([]int, error) {
if !g.HasNode(nodeid) {
return []int{}, ErrNodeNotFound{nodeid}
}
return g.fadjlist[nodeid], nil
}
Next I have a wrapper around it for a metagraph type to store metadata for each node. The metadata I'll be storing is the bfsdata type.
type bfsdata struct {
Color int
Depth int
}
type metagraph[T any] struct {
G *graph
metadata map[int]T
}
And I have a setter and getter for the metadata.
func (mg *metagraph[T]) Data(v int) (T, error) {
if !mg.G.HasNode(v) {
return mg.metadata[v], ErrNodeNotFound{v}
}
return mg.metadata[v], nil
}
func (mg *metagraph[T]) SetData(v int, data T) (T, error) {
if !mg.G.HasNode(v) {
return mg.metadata[v], ErrNodeNotFound{v}
}
mg.metadata[v] = data
return mg.metadata[v], nil
}
Now I can finally come to the actual logic section of my code. I have a function to compute a BFS tree as a MetaGraph given a graph and a root node. I start at the root node, and I pass the node to the ProcessChildren function. There, I assign each child that has not been visited before a depth of parent.Depth + 1. If the child has the same color as the parent, that means the graph is not bipartite, and I return false. Otherwise I return true. Finally, I queue up all these children to be processed. Each call to the bfs function returns the max depth of the tree.
func ProcessChildren(mg metagraph[bfsdata], parent int, checked map[int]bool) bool {
children, e := mg.G.Neighbours(parent)
if e != nil {
panic(e)
}
mydata, err := mg.Data(parent)
if err != nil {
return false
}
for _, child := range children {
if checked[child] {
continue
}
childdata, e := mg.Data(child)
if e != nil {
return false
} else if childdata.Color == mydata.Color {
return false
}
mg.SetData(child, bfsdata{Color: -1 * mydata.Color, Depth: mydata.Depth + 1})
}
return true
}
type ErrNotBipartite struct {
parent int
}
func (e ErrNotBipartite) Error() string {
return fmt.Sprintf("Node %d connects to nodes in the same partition", e.parent)
}
func bfs(g graph, root int) (metagraph[bfsdata], int, error) {
mg := metagraph[bfsdata]{&g, make(map[int]bfsdata)}
mg.SetData(root, bfsdata{Color: -1, Depth: 0})
// Root myself at the first node, start bfs
tocheck := []int{root}
maxdepth := 0
_, e := mg.G.Neighbours(root)
if e != nil {
panic(e)
}
checked := make(map[int]bool)
for len(tocheck) > 0 {
checkme := tocheck[0]
tocheck = tocheck[1:]
if checked[checkme] {
continue
}
if !ProcessChildren(mg, checkme, checked) {
return mg, -1, ErrNotBipartite{checkme}
}
mydata, _ := mg.Data(checkme)
if maxdepth < mydata.Depth {
maxdepth = mydata.Depth
}
nlist, _ := mg.G.Neighbours(checkme)
tocheck = append(tocheck, nlist...)
checked[checkme] = true
}
return mg, maxdepth, nil
}
- Here's a link to the actual question.
- Here's a link to the full code on Go Playground, with some test cases that return the correct result
My code is correct, just slow it seems? I'm not a programmer by training, I'm a physicist by education and sysadmin by profession, with an interest in programming.
The problem, as I understand it, is that given a graph composed of connected subgraphs, find the sum of the maximum depths of the BFS tree for each component. My procedure for solving this is as follows.
- Find all the connected subgraphs using a Union Find
- For each subgraph, construct a BFS tree from each vertex and return the maximum depth possible. Ensure the graph is bipartite while computing the BFS tree.
The main logic is in this function, and everything this function depends on is written below. I construct an adjacency list backed graph from the list of edges, compute all the connected subgraphs using a Union-Find, and for each subgraph (represented as a list of vertices), run a BFS rooted at each vertex to find the deepest tree possible. Finally I return the sum of the depths of all deepest trees.
func magnificentSets(n int, edges [][]int) int {
// Construct graph
g := GraphWithCapacity(n)
set := DisjointSetWiithCapacity(n)
for _, e := range edges {
src := e[0] - 1
dst := e[1] - 1
if !g.AddEdge(src, dst) {
fmt.Printf("Unable to add edge {%d, %d}\n.", src, dst)
}
set.Union(src, dst)
}
connected_subgraphs := make(map[int][]int)
for n := range g.EachNode() {
p := set.Find(n)
connected_subgraphs[p] = append(connected_subgraphs[p], n)
}
total_maxdepths := 0
for _, vlist := range connected_subgraphs {
if len(vlist) == 1 {
total_maxdepths += 1
continue
}
maxdepth := 0
for _, v := range vlist {
_, depthatv, err := bfs(g, v)
if err != nil {
fmt.Println(err.Error())
return -1
}
if depthatv > maxdepth {
maxdepth = depthatv
}
}
total_maxdepths += maxdepth + 1
}
return total_maxdepths
}
Here's my code broken down and explained. I have a data structure for the union-find part, which consists of a factory to initialize with a given number of nodes, and the Union and Find functions on it.
type disjoint_set struct {
parent []int
}
func DisjointSetWiithCapacity(n int) disjoint_set {
parent := make([]int, n)
for idx := range parent {
parent[idx] = idx
}
return disjoint_set{parent}
}
func (uf *disjoint_set) Find(node int) int {
cnode := node
for uf.parent[cnode] != cnode {
cnode = uf.parent[cnode]
}
uf.parent[node] = cnode
return cnode
}
func (uf *disjoint_set) Union(node_1, node_2 int) bool {
p1 := uf.Find(node_1)
p2 := uf.Find(node_2)
if p1 == p2 {
return false
}
child := max(p1, p2)
parent := min(p1, p2)
uf.parent[child] = parent
return true
}
Then I have a graph data structure representing my graph as a full adjacency list.
type ErrNodeNotFound struct {
nodeid int
}
func (e ErrNodeNotFound) Error() string {
return fmt.Sprintf("Node %d not found in graph.\n", e.nodeid)
}
type graph struct {
fadjlist [][]int
}
func GraphWithCapacity(cap int) graph {
return graph{fadjlist: make([][]int, cap)}
}
I have methods on it to
- Add a node
- Add an edge
- Check if node exists
- Compute neighbors of a node
- Iterators over nodes and edges
func (g *graph) AddNode() int {
g.fadjlist = append(g.fadjlist, make([]int, 0))
return len(g.fadjlist) - 1
}
func (g *graph) HasNode(nodeid int) bool {
return nodeid < len(g.fadjlist)
}
func (g *graph) EachNode() iter.Seq[int] {
return func(yield func(int) bool) {
for i := 0; i < len(g.fadjlist); i += 1 {
if !yield(i) {
return
}
}
}
}
func (g *graph) EachEdge() iter.Seq2[int, int] {
return func(yield func(int, int) bool) {
for src, adjlist := range g.fadjlist {
for _, dst := range adjlist {
if dst > src {
continue
}
if !yield(src, dst) {
return
}
}
}
}
}
func (g *graph) AddEdge(from, to int) bool {
src := min(from, to)
dst := max(from, to)
if !g.HasNode(src) || !g.HasNode(dst) {
return false
}
if slices.Contains(g.fadjlist[src], dst) {
return false
}
g.fadjlist[src] = append(g.fadjlist[src], dst)
g.fadjlist[dst] = append(g.fadjlist[dst], src)
return true
}
func (g *graph) Neighbours(nodeid int) ([]int, error) {
if !g.HasNode(nodeid) {
return []int{}, ErrNodeNotFound{nodeid}
}
return g.fadjlist[nodeid], nil
}
Next I have a wrapper around it for a metagraph type to store metadata for each node. The metadata I'll be storing is the bfsdata type.
type bfsdata struct {
Color int
Depth int
}
type metagraph[T any] struct {
G *graph
metadata map[int]T
}
And I have a setter and getter for the metadata.
func (mg *metagraph[T]) Data(v int) (T, error) {
if !mg.G.HasNode(v) {
return mg.metadata[v], ErrNodeNotFound{v}
}
return mg.metadata[v], nil
}
func (mg *metagraph[T]) SetData(v int, data T) (T, error) {
if !mg.G.HasNode(v) {
return mg.metadata[v], ErrNodeNotFound{v}
}
mg.metadata[v] = data
return mg.metadata[v], nil
}
Now I can finally come to the actual logic section of my code. I have a function to compute a BFS tree as a MetaGraph given a graph and a root node. I start at the root node, and I pass the node to the ProcessChildren function. There, I assign each child that has not been visited before a depth of parent.Depth + 1. If the child has the same color as the parent, that means the graph is not bipartite, and I return false. Otherwise I return true. Finally, I queue up all these children to be processed. Each call to the bfs function returns the max depth of the tree.
func ProcessChildren(mg metagraph[bfsdata], parent int, checked map[int]bool) bool {
children, e := mg.G.Neighbours(parent)
if e != nil {
panic(e)
}
mydata, err := mg.Data(parent)
if err != nil {
return false
}
for _, child := range children {
if checked[child] {
continue
}
childdata, e := mg.Data(child)
if e != nil {
return false
} else if childdata.Color == mydata.Color {
return false
}
mg.SetData(child, bfsdata{Color: -1 * mydata.Color, Depth: mydata.Depth + 1})
}
return true
}
type ErrNotBipartite struct {
parent int
}
func (e ErrNotBipartite) Error() string {
return fmt.Sprintf("Node %d connects to nodes in the same partition", e.parent)
}
func bfs(g graph, root int) (metagraph[bfsdata], int, error) {
mg := metagraph[bfsdata]{&g, make(map[int]bfsdata)}
mg.SetData(root, bfsdata{Color: -1, Depth: 0})
// Root myself at the first node, start bfs
tocheck := []int{root}
maxdepth := 0
_, e := mg.G.Neighbours(root)
if e != nil {
panic(e)
}
checked := make(map[int]bool)
for len(tocheck) > 0 {
checkme := tocheck[0]
tocheck = tocheck[1:]
if checked[checkme] {
continue
}
if !ProcessChildren(mg, checkme, checked) {
return mg, -1, ErrNotBipartite{checkme}
}
mydata, _ := mg.Data(checkme)
if maxdepth < mydata.Depth {
maxdepth = mydata.Depth
}
nlist, _ := mg.G.Neighbours(checkme)
tocheck = append(tocheck, nlist...)
checked[checkme] = true
}
return mg, maxdepth, nil
}
- At a glance, the code seems way too complicated for the problem it's solving. – Unmitigated Commented Feb 2 at 5:14
- @Unmitigated if you could add your comment as an answer then I can accept your answer since I figured out the issue thanks to you. – user29447151 Commented Feb 6 at 11:17
- Glad to see you figured it out. The content of my comment isn't really enough for a full-fledged answer (it was just a pointer in the right direction, but you did most of the work yourself), but you can accept your own answer. – Unmitigated Commented Feb 8 at 6:08
1 Answer
Reset to default 0@unmitigated's comment made me remove all the fluff in my code and it seems to have sped it up. TIL that the compiler doesn't just remove/inline functions that you write for convenience so those functions make things slower.
I also realized I don't need to do the union find pass because BFS will automatically find all connected components. Here's the solution with just BFS in Go. It's still quite slow, so if anybody would like to optimize, please go ahead and I'd love to learn.
package main
import (
"fmt"
)
type bfsdata struct {
Color int
Depth int
}
func ProcessChildren(fadjlist [][]int, metadata []bfsdata, parent int, checked map[int]bool) bool {
children := fadjlist[parent]
mydata := metadata[parent]
for _, child := range children {
if checked[child] {
continue
}
childdata := metadata[child]
if childdata.Color == mydata.Color {
return false
}
metadata[child].Color = -1 * mydata.Color
metadata[child].Depth = mydata.Depth + 1
}
return true
}
type ErrNotBipartite struct {
parent int
}
func (e ErrNotBipartite) Error() string {
return fmt.Sprintf("Node %d connects to nodes in the same partition", e.parent)
}
func bfs(fadjlist [][]int, root int, cache []int) (map[int]bool, int, error) {
metadata := make([]bfsdata, len(fadjlist))
metadata[root] = bfsdata{Color: -1, Depth: 0}
// Root myself at the first node, start bfs
tocheck := cache[0:0]
tocheck = append(tocheck, root)
maxdepth := 0
checked := make(map[int]bool)
for len(tocheck) > 0 {
checkme := tocheck[0]
tocheck = tocheck[1:]
if checked[checkme] {
continue
}
if !ProcessChildren(fadjlist, metadata, checkme, checked) {
return checked, -1, ErrNotBipartite{checkme}
}
mydata := metadata[checkme]
if maxdepth < mydata.Depth {
maxdepth = mydata.Depth
}
nlist := fadjlist[checkme]
tocheck = append(tocheck, nlist...)
checked[checkme] = true
}
return checked, maxdepth, nil
}
func magnificentSets(n int, edges [][]int) int {
// Construct graph
g := make([][]int, n)
for _, e := range edges {
src := e[0] - 1
dst := e[1] - 1
g[src] = append(g[src], dst)
g[dst] = append(g[dst], src)
}
total_maxdepths := 0
tocheck := make([]int, 0, 8)
visited := make(map[int]bool)
for v := range g {
if visited[v] {
continue
}
connected_subgraph, depthatv, err := bfs(g, v, tocheck)
if err != nil {
fmt.Println(err.Error())
return -1
}
// Check this connected subgraph
maxdepth := depthatv
for v_prime := range connected_subgraph {
if v_prime == v {
continue
}
_, depth_at_vprime, _ := bfs(g, v_prime, tocheck)
if depth_at_vprime > maxdepth {
maxdepth = depth_at_vprime
}
}
// Append the nodes we've already touched
for node := range connected_subgraph {
visited[node] = true
}
total_maxdepths += maxdepth + 1
}
return total_maxdepths
}
func main() {
nnodes := 6
data := [][]int{{1, 2}, {1, 4}, {1, 5}, {2, 6}, {2, 3}, {4, 6}}
fmt.Println("Max depth of BFS tree: ", magnificentSets(nnodes, data))
nnodes = 3
data = [][]int{{1, 2}, {2, 3}, {3, 1}}
fmt.Println("Max depth of BFS tree: ", magnificentSets(nnodes, data))
nnodes = 92
data = [][]int{{67, 29}, {13, 29}, {77, 29}, {36, 29}, {82, 29}, {54, 29}, {57, 29}, {53, 29}, {68, 29}, {26, 29}, {21, 29}, {46, 29}, {41, 29}, {45, 29}, {56, 29}, {88, 29}, {2, 29}, {7, 29}, {5, 29}, {16, 29}, {37, 29}, {50, 29}, {79, 29}, {91, 29}, {48, 29}, {87, 29}, {25, 29}, {80, 29}, {71, 29}, {9, 29}, {78, 29}, {33, 29}, {4, 29}, {44, 29}, {72, 29}, {65, 29}, {61, 29}}
fmt.Println("Max depth of BFS tree: ", magnificentSets(nnodes, data))
// [[67, 29], [13, 29], [77, 29], [36, 29], [82, 29], [54, 29], [57, 29], [53, 29], [68, 29], [26, 29], [21, 29], [46, 29], [41, 29], [45, 29], [56, 29], [88, 29], [2, 29], [7, 29], [5, 29], [16, 29], [37, 29], [50, 29], [79, 29], [91, 29], [48, 29], [87, 29], [25, 29], [80, 29], [71, 29], [9, 29], [78, 29], [33, 29], [4, 29], [44, 29], [72, 29], [65, 29], [61, 29]]
nnodes = 30
data = [][]int{{1, 4}, {1, 5}, {1, 6}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3, 6}, {6, 7}, {7, 11}, {8, 11}, {8, 12}, {8, 13}, {9, 11}, {9, 12}, {9, 13}, {10, 11}, {10, 12}, {10, 13}}
fmt.Println("Max depth of BFS tree: ", magnificentSets(nnodes, data))
}
本文标签： goLeetCode Time limit exceeded on Graph question 2493Stack Overflow
版权声明：本文标题：go - LeetCode Time limit exceeded on Graph question 2493 - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1741916595a2404770.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论