Introduction

An undirected graph is "broken" when vertices that used to be reachable from each other are now split into separate connected components. This matters in routing, network monitoring, and dependency analysis because a disconnected graph often means some part of the system is no longer usable.

Count Components with DFS or BFS

The simplest test is to count connected components. If the count is greater than 1, the graph is disconnected. A depth-first search or breadth-first search works well because each vertex and edge is visited at most once.

With an adjacency list, the algorithm is:

1. Build neighbors for every vertex.
2. Keep a visited set.
3. Start a traversal from each unvisited vertex.
4. Increment a counter every time a new traversal starts.

That counter is the number of connected components.

1from collections import defaultdict
2
3
4def count_components(vertex_count, edges):
5    graph = defaultdict(list)
6    for a, b in edges:
7        graph[a].append(b)
8        graph[b].append(a)
9
10    visited = set()
11    components = 0
12
13    for start in range(vertex_count):
14        if start in visited:
15            continue
16
17        components += 1
18        stack = [start]
19
20        while stack:
21            node = stack.pop()
22            if node in visited:
23                continue
24
25            visited.add(node)
26            for neighbor in graph[node]:
27                if neighbor not in visited:
28                    stack.append(neighbor)
29
30    return components
31
32
33edges = [(0, 1), (1, 2), (3, 4)]
34print(count_components(5, edges))  # 2

If you only need a yes or no answer, you can stop early as soon as the second component is found.

1def is_broken(vertex_count, edges):
2    return count_components(vertex_count, edges) > 1
3
4
5print(is_broken(5, edges))  # True

This approach is O(V + E) time and O(V + E) space, which is usually the right baseline solution.

Detect Whether Removing One Edge Breaks the Graph

Sometimes the graph is currently connected, and the real question is whether a specific failure will split it. In graph theory, an edge with that property is a bridge. For a single edge check, a direct approach is to remove that edge and count components again.

1def breaks_after_removal(vertex_count, edges, removed_edge):
2    a, b = removed_edge
3    remaining = []
4    removed = False
5
6    for x, y in edges:
7        if not removed and ((x, y) == (a, b) or (x, y) == (b, a)):
8            removed = True
9            continue
10        remaining.append((x, y))
11
12    return count_components(vertex_count, remaining) > 1
13
14
15connected_edges = [(0, 1), (1, 2), (2, 3)]
16print(breaks_after_removal(4, connected_edges, (1, 2)))  # True
17print(breaks_after_removal(4, [(0, 1), (1, 2), (2, 0)], (1, 2)))  # False

This is fine for one-off checks, but it becomes expensive if you need to test many edges because you repeat a full traversal every time. In that case, compute all bridges once with Tarjan's algorithm. Tarjan's method also runs in O(V + E) time, but it returns every edge whose removal disconnects the graph.

The key idea is to track:

• 'disc[node]: when a node was first visited'
• 'low[node]: the earliest reachable discovery time from that node'

If a child cannot reach an ancestor of its parent, then the edge between parent and child is a bridge. That is the efficient choice for repeated failure analysis.

Practical Modeling Details

The exact definition of "broken" depends on the graph model:

• In an undirected graph, connected components are the standard answer.
• In a directed graph, you must decide between weakly connected and strongly connected components.
• If some vertices are isolated but expected, you may only care whether a specific subset remains connected.

A monitoring system for servers, for example, may treat a graph as broken only if two active data centers can no longer reach each other. A graph processing library cannot guess that business rule, so define it explicitly before coding.

Common Pitfalls

• Forgetting isolated vertices. A vertex with no edges is still its own component, so looping only over adjacency keys can undercount.
• Mixing directed and undirected logic. If the graph is directed, reusing undirected traversal code may hide the real failure mode.
• Recomputing from scratch for every edge query. That works for small inputs, but a bridge-finding algorithm is much better when many removals must be tested.
• Mutating shared adjacency structures carelessly. Removing an edge in place can affect later checks if the original graph is needed again.

Summary

• A graph is broken when it has more than one connected component.
• DFS and BFS detect disconnection in O(V + E) time.
• For a single failure check, remove the edge and recount components.
• For many failure checks, compute bridges once instead of repeating full traversals.
• Be explicit about whether the graph is undirected, directed, or only partially relevant.