Problem
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.
Examples
Example 1
Input:
Adjacency List: {
0: [1, 2],
1: [0, 3, 4],
2: [0],
3: [1],
4: [1]
}
Output: true
Explanation: The graph is minimally connected, representing a tree.
Example 2
Input:
Adjacency List: {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1, 3],
3: [1, 2]
}
Output: false
Explanation: The graph contains cycles and removing edges can still leave the graph connected.
Solution
Method 1 - Using DFS
To check if a graph is minimally-connected, we need to:
- Check Connectivity: Ensure all nodes are reachable from any starting node.
- Check Acyclic Property: Verify that removing any edge would disconnect the graph. This implies that the graph has
n-1
edges forn
nodes (property of a tree).
Approach
- Ensure all nodes are visited starting from any node.
- Verify if the graph has exactly
n-1
edges forn
nodes.
Code
Java
public class Solution {
public boolean isMinimallyConnected(Map<Integer, List<Integer>> adjList) {
int nodes = adjList.size();
boolean[] visited = new boolean[nodes];
if (!isConnected(adjList, visited)) return false;
int edgeCount = 0;
for (List<Integer> neighbors : adjList.values()) {
edgeCount += neighbors.size();
}
edgeCount /= 2; // because each edge is counted twice
return edgeCount == nodes - 1;
}
private boolean isConnected(Map<Integer, List<Integer>> adjList, boolean[] visited) {
int nodes = visited.length;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
visited[0] = true;
int visitedCount = 1;
while (!stack.isEmpty()) {
int node = stack.pop();
for (int neighbor : adjList.get(node)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
visitedCount++;
}
}
}
return visitedCount == nodes;
}
public static void main(String[] args) {
Solution solution = new Solution();
Map<Integer, List<Integer>> adjList1 = new HashMap<>();
adjList1.put(0, Arrays.asList(1, 2));
adjList1.put(1, Arrays.asList(0, 3, 4));
adjList1.put(2, Arrays.asList(0));
adjList1.put(3, Arrays.asList(1));
adjList1.put(4, Arrays.asList(1));
System.out.println(solution.isMinimallyConnected(adjList1)); // true
}
}
Python
class Solution:
def is_minimally_connected(self, adj_list: Dict[int, List[int]]) -> bool:
nodes = len(adj_list)
visited = [False] * nodes
if not self.is_connected(adj_list, visited):
return False
edge_count = sum(len(neighbors) for neighbors in adj_list.values()) // 2
return edge_count == nodes - 1
def is_connected(self, adj_list: Dict[int, List[int]], visited: List[bool]) -> bool:
nodes = len(visited)
stack = [0]
visited[0] = True
visited_count = 1
while stack:
node = stack.pop()
for neighbor in adj_list[node]:
if not visited[neighbor]:
visited[neighbor] = True
stack.append(neighbor)
visited_count += 1
return visited_count == nodes
# Example usage
sol = Solution()
adj_list1 = {
0: [1, 2],
1: [0, 3, 4],
2: [0],
3: [1],
4: [1]
}
print(sol.is_minimally_connected(adj_list1)) # Output: True
Complexity
- ⏰ Time complexity:
O(V + E)
for DFS or Union-Find whereV
is the number of vertices andE
is the number of edges. - 🧺 Space complexity:
O(V)
for storing visited nodes or parent and rank arrays for Union-Find.