Graphs

Nodes and edges modeling networks, dependencies, and paths.

Graphs Practice Problems

Easy

4 problems
  1. 440

    Find Center of Star Graph

    Spot the middle node of a star-shaped graph by comparing only the first two edges, with no counting and no traversal.

    easy
  2. 441

    Find the Town Judge

    Give every person one score built from who trusts whom, then read off the only person who trusts nobody and is trusted by all.

    easy
  3. 442

    Keys and Rooms

    Use a stack to open rooms with the keys you collect, and decide whether every room can be reached from room 0.

    easy
  4. 443

    Max Area of Island

    Treat a grid of ones and zeros as a graph and flood fill each island, sinking cells as you count, to find the largest one.

    easy

Medium

4 problems
  1. 444

    Clone Graph

    Make a deep copy of a graph that contains cycles by keeping a map from each original node to the single copy that stands for it.

    medium
  2. 445

    Is Graph Bipartite

    Paint the graph in two colours with a breadth-first walk and decide whether the nodes split into two groups with no edge inside a group.

    medium
  3. 446

    All Paths From Source to Target

    List every route from the first node to the last in a directed graph with no cycles, using backtracking to undo one move at a time.

    medium
  4. 447

    Minimum Number of Vertices to Reach All Nodes

    Find the smallest set of starting nodes that reaches everything by collecting exactly the nodes with no arrow pointing at them.

    medium

Hard

2 problems
  1. 448

    Critical Connections in a Network

    Find every bridge in a network using discovery times and low-link values from a single depth-first walk.

    hard
  2. 449

    Reconstruct Itinerary

    Order a pile of airline tickets into one trip from JFK that uses every ticket once, picking the alphabetically smallest valid route.

    hard

Related concepts