Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 182
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

A graph is minimally-connected if it is connected and there is no edge that can be removed while still leaving the graph connected. For example, any binary tree is minimally-connected.

Given an undirected graph, check if the graph is minimally-connected. You can choose to represent the graph as either an adjacency matrix or adjacency list.

Pull request description:
Day182
Resolves #376.

Patch:
diff --git a/README.md b/README.md
index 081950b..5120046 100644
--- a/README.md
+++ b/README.md
@@ -191,4 +191,5 @@ problems from
 * [Day 178](https://github.com/vaskoz/dailycodingproblem-go/issues/367)
 * [Day 179](https://github.com/vaskoz/dailycodingproblem-go/issues/371)
 * [Day 180](https://github.com/vaskoz/dailycodingproblem-go/issues/373)
+* [Day 182](https://github.com/vaskoz/dailycodingproblem-go/issues/376)
 * [Day 184](https://github.com/vaskoz/dailycodingproblem-go/issues/378)
diff --git a/day182/problem.go b/day182/problem.go
new file mode 100644
index 0000000..a1101b1
--- /dev/null
+++ b/day182/problem.go
@@ -0,0 +1,48 @@
+package day182
+
+// Node represents a node in an undirected graph.
+type Node string
+
+// UndirectedGraph is an undirected graph of nodes.
+// Edges go in both directions since it's undirected.
+type UndirectedGraph map[Node]map[Node]struct{}
+
+// IsMinimallyConnected answers if the graph is minimally connected.
+// Basically runs DFS.
+func IsMinimallyConnected(g UndirectedGraph) bool {
+	visited := make(map[Node]struct{})
+	if edges := countEdges(g); edges != (len(g)-1)*2 {
+		return false
+	}
+	start := randomNode(g)
+	isConnected(g, start, visited)
+	return len(visited) == len(g)
+}
+
+func randomNode(g UndirectedGraph) Node {
+	var n Node
+	for x := range g {
+		n = x
+		break
+	}
+	return n
+}
+
+func isConnected(g UndirectedGraph, start Node, visited map[Node]struct{}) {
+	visited[start] = struct{}{}
+	for dest := range g[start] {
+		if _, found := visited[dest]; !found {
+			isConnected(g, dest, visited)
+		}
+	}
+}
+
+func countEdges(g UndirectedGraph) int {
+	count := 0
+	for _, targets := range g {
+		for range targets {
+			count++
+		}
+	}
+	return count
+}


Test patch:
diff --git a/day182/problem_test.go b/day182/problem_test.go
new file mode 100644
index 0000000..b68fd3a
--- /dev/null
+++ b/day182/problem_test.go
@@ -0,0 +1,56 @@
+package day182
+
+import "testing"
+
+var testcases = []struct {
+	g        UndirectedGraph
+	expected bool
+}{
+	{UndirectedGraph{
+		"a": {},
+		"b": {},
+	}, false},
+	{UndirectedGraph{
+		"a": {"b": struct{}{}},
+		"b": {"a": struct{}{}},
+	}, true},
+	{UndirectedGraph{
+		"a": {"b": struct{}{}},
+		"b": {
+			"a": struct{}{},
+			"c": struct{}{},
+		},
+		"c": {"b": struct{}{}},
+	}, true},
+	{UndirectedGraph{
+		"a": {
+			"b": struct{}{},
+			"c": struct{}{},
+		},
+		"b": {
+			"a": struct{}{},
+			"c": struct{}{},
+		},
+		"c": {
+			"a": struct{}{},
+			"b": struct{}{},
+		},
+	}, false},
+}
+
+func TestIsMinimallyConnected(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := IsMinimallyConnected(tc.g); result != tc.expected {
+			t.Errorf("TCID%d Expected %v, got %v", tcid, tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkIsMinimallyConnected(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IsMinimallyConnected(tc.g)
+		}
+	}
+}