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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6
7
8
9

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:

  1. Check Connectivity: Ensure all nodes are reachable from any starting node.
  2. Check Acyclic Property: Verify that removing any edge would disconnect the graph. This implies that the graph has n-1 edges for n nodes (property of a tree).

Approach

  • Ensure all nodes are visited starting from any node.
  • Verify if the graph has exactly n-1 edges for n nodes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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 where V is the number of vertices and E is the number of edges.
  • 🧺 Space complexity: O(V) for storing visited nodes or parent and rank arrays for Union-Find.