pyPython Practice LabFrom first print to final round
TOPIC 16 OF 18

Graphs and Connectivity Python practice problems

Graph representation, BFS, DFS, shortest paths, topological order, and union-find.

28 exercises8+ conceptsBeginner → interview context
Start this topic
WHAT YOU WILL PRACTISE

Core concepts

Traverse a graph with BFSFind an unweighted shortest pathCount islands in a gridTopologically sort tasksCount connected components with union-findFind a redundant graph edgeCheck if courses can be completedClone an undirected graph
REUSABLE THINKING

Problem-solving patterns

  • graph · BFS
  • shortest path · parent map
  • DFS · grid
  • topological sort · Kahn
  • union-find · graph · company screen
PRACTICE OUTCOME

What this topic builds

Learn the idea once, use it across the exercises, and explain why your approach works.

ORDERED PRACTICE

All 28 problems in this topic

Work from top to bottom to build the concept gradually.

  1. #299
    Traverse a graph with BFS: Connected graph

    Visit a connected graph from vertex zero in deterministic neighbor order.

    BeginnerPremium
  2. #300
    Traverse a graph with BFS: Disconnected graph

    Visit only the component reachable from the chosen start.

    BeginnerPremium
  3. #301
    Find an unweighted shortest path: Route exists

    Find a shortest route in a small unweighted network.

    IntermediatePremium
  4. #302
    Find an unweighted shortest path: Unreachable destination

    Report when start and target lie in disconnected components.

    IntermediatePremium
  5. #303
    Count islands in a grid: Three islands

    Count separate land regions in a small map.

    IntermediatePremium
  6. #304
    Count islands in a grid: All water

    Return zero when the grid contains no land.

    IntermediatePremium
  7. #305
    Topologically sort tasks: Valid build order

    Produce one valid order for tasks with prerequisites.

    IntermediatePremium
  8. #306
    Topologically sort tasks: Cyclic dependencies

    Report Cycle when no complete topological order exists.

    AdvancedPremium
  9. #307
    Count connected components with union-find: Two graph components

    Count groups of vertices connected by undirected edges.

    AdvancedPremium
  10. #308
    Count connected components with union-find: No edges

    Every isolated vertex forms its own component.

    AdvancedPremium
  11. #309
    Find a redundant graph edge: Triangle cycle

    Find the final edge that closes a cycle in an almost-tree graph.

    AdvancedPremium
  12. #310
    Find a redundant graph edge: Longer cycle

    Detect the edge that reconnects vertices already joined through another route.

    AdvancedPremium
  13. #311
    Check if courses can be completed: Acyclic prerequisites

    Determine that every course can be completed in some valid order.

    AdvancedPremium
  14. #312
    Check if courses can be completed: Circular prerequisites

    Reject a plan where two courses depend on each other.

    AdvancedPremium
  15. #313
    Clone an undirected graph: Connected graph clone

    Deep-copy an undirected graph and print the clone's adjacency list.

    Interview-LevelPremium
  16. #314
    Clone an undirected graph: Include isolated node

    Preserve a vertex even when it has no neighbors.

    Interview-LevelPremium
  17. #315
    Merge accounts by shared email: Shared email merge

    Combine account rows that belong to the same person through a shared email.

    Interview-LevelPremium
  18. #316
    Merge accounts by shared email: No shared emails

    Keep every account separate when no email appears twice.

    Interview-LevelPremium
  19. #317
    Find a word-ladder length: Reachable transformation

    Find the shortest valid sequence from hit to cog.

    Interview-LevelPremium
  20. #318
    Find a word-ladder length: Missing destination

    Return zero when the destination is absent from the dictionary.

    Interview-LevelPremium
  21. #319
    Evaluate division queries: Connected ratios

    Evaluate direct, inverse, chained, and unknown division queries.

    Interview-LevelPremium
  22. #320
    Evaluate division queries: Disconnected variables

    Return -1 when no path connects two known variables.

    Interview-LevelPremium
  23. #321
    Find network delay time: All nodes reached

    Find how long a signal takes to reach every node in a weighted network.

    Interview-LevelPremium
  24. #322
    Find network delay time: Unreachable node

    Return -1 when at least one node cannot receive the signal.

    Interview-LevelPremium
  25. #323
    Find cheapest flight with stop limit: Cheaper one-stop route

    Choose a cheaper route that uses one allowed stop.

    Interview-LevelPremium
  26. #324
    Find cheapest flight with stop limit: Stop limit blocks route

    Return the direct price when a cheaper multi-edge route uses too many stops.

    Interview-LevelPremium
  27. #325
    Infer an alien alphabet: Valid alien order

    Infer one deterministic character order from a sorted alien dictionary.

    Interview-LevelPremium
  28. #326
    Infer an alien alphabet: Invalid prefix order

    Reject a longer word that incorrectly appears before its exact prefix.

    Interview-LevelPremium