Maximum Subgraph: Find the Largest Connected Subgraph Satisfying a Node Constraint

Question

## Problem

Given an undirected graph where each node has a label, find the largest connected subgraph where all nodes share the same label. "Largest" means the most nodes.

```python
def max_same_label_subgraph(
    n: int,
    edges: list[tuple[int,int]],
    labels: list[str]
) -> tuple[str, list[int]]:
    # returns: (label, list of node IDs in the largest same-label component)
    pass
```

**Example:**
```
n = 6
edges = [(0,1),(1,2),(2,3),(3,4),(4,5)]
labels = ["A","A","A","B","B","A"]
# Component {0,1,2} all label A -> size 3
# Component {5} label A -> size 1
# Component {3,4} label B -> size 2
result -> ("A", [0, 1, 2])
```

## Follow-ups

1. How does your BFS/DFS handle disconnected graphs (multiple components)?
2. What is the time and space complexity of your solution?
3. How would you extend this to find the largest subgraph where nodes satisfy a predicate (e.g., label in {A, B})?
4. If edges are weighted, how would you find the subgraph with the maximum total edge weight?

Maximum Subgraph: Find the Largest Connected Subgraph Satisfying a Node Constraint

Question Details

Full Details

Topics

More from Waymo