Curated sets
Graphs and traversal
BFS, DFS, shortest paths, and trees.
Total results3,710 problems
| Topics | Judge | |||||
|---|---|---|---|---|---|---|
| Your lifeFind the fewest directed moves from node 1 to node N in a graph where every edge goes forward, or report -1 when the goal is unreachable. | Easy3 | BFSShortest path+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Rings of SaturnFind every connected group of exactly seven people, sum the threat levels inside each group, and list them by total threat. | Easy3 | Union-findSorting | No attempts yet | 2s | 256 MB | Judgeable |
| One sheep... two sheep...Count the groups of # cells connected up, down, left, or right in each test grid. | Easy3 | DFSGraph+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Neurotic NetworkEvaluate the weighted sum from the leaves to the root of a tree and print FREAK OUT for an even result, else the value modulo 1,000,000,007. | Easy3 | TreeDynamic programming+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Pub-lic GoodColor each site pub or house with the specified ordered depth-first search so every site neighbors an opposite color, or print Impossible. | Easy3 | DFSGraph+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Travel of AlphabetsCount all length-L walks on a letter grid and the distinct strings among them, discarding any word containing a, c, or m. | Easy3 | BacktrackingDFS+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Spawn of UngoliantSpiders spread to every tree connected by four-directional adjacency to an infested tree, and isolated trees and open floor stay unchanged. | Easy3 | BFSGraph+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Path FindingDecide for every ordered pair of vertices in a directed graph with up to 100 vertices whether a path of at least one edge connects them. | Easy3 | GraphDynamic programming | No attempts yet | 1s | 256 MB | Judgeable |
| Manhattan Power FailureCount the blocks linked by intact lines into regions and report how many regions hold no generator. | Easy3 | Union-findGraph | No attempts yet | 1s | 256 MB | Judgeable |
| The Game of DeathStarting from player 1, follow the pointed-to players and report the first step that reaches player N, or 0 when it never does. | Easy3 | GraphSimulation | No attempts yet | 1s | 256 MB | Judgeable |
| Relief SuppliesDecide whether any walk starting at intersection 1 in a directed graph can revisit an intersection. | Easy3 | DFSGraph | No attempts yet | 2s | 256 MB | Judgeable |
| Number of connected componentsCount the connected components of an undirected graph given its vertices and edges. | Easy3 | GraphDFS | No attempts yet | 3s | 512 MB | Judgeable |
| Finding Parents in a TreeStarting from node 1 as the root, print the parent of every other node in the given tree. | Easy3 | BFSTree | No attempts yet | 1s | 256 MB | Judgeable |
| Squawk VirusStarting from user s, propagate squawk counts along links for t minutes and report how many squawks are sent at time t. | Easy3 | Dynamic programmingGraph | No attempts yet | 1s | 256 MB | Judgeable |
| Orienting Molecular BondsDirect every tree edge from the endpoint at even distance from node 1 to the one at odd distance. | Easy3 | BFSTree | No attempts yet | 1s | 64 MB | Judgeable |
| Array EscapeFind the cheapest right-and-down path through a square grid where stepping to a higher or equal neighbor costs the raises needed to exceed it. | Easy3 | Dynamic programmingShortest path+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Dynamic Grid (Small)Count the edge-connected groups of 1s in a binary grid after each point update by flood fill. | Easy3 | BFSGraph+1 | No attempts yet | 5s | 512 MB | Judgeable |
| Bad Horse (Small 1)Decide for each test case whether members joined by troublesome pairs split into two groups with no pair in one group. | Easy3 | GraphBFS | No attempts yet | 5s | 512 MB | Judgeable |
| Bad Horse (Small2)Decide whether members linked by troublesome pairs split into two groups with no pair inside one group. | Easy3 | GraphBFS | No attempts yet | 5s | 512 MB | Judgeable |
| Sort a scrambled itinerary (Small)Rebuild each shuffled set of flight tickets into the single chain where each arrival matches the next departure. | Easy3 | Hash mapGraph | No attempts yet | 5s | 512 MB | Judgeable |
| Twibet (Small)Starting from each monk in turn, count how many monks hear a whisper that spreads from a monk to all direct and indirect followers. | Easy3 | GraphDFS | No attempts yet | 5s | 512 MB | Judgeable |
| Ping Pong Balls (Small)Given two fixed displacement vectors, simulate the chain reaction from one starting trap and count how many distinct traps fire. | Easy3 | SimulationBFS+2 | No attempts yet | 5s | 512 MB | Judgeable |
| Modern Art Plagiarism (Small)Decide whether the smaller tree is a connected subgraph of the larger tree, with only the shapes mattering, not the original labels. | Easy3 | TreeBacktracking | No attempts yet | 5s | 512 MB | Judgeable |
| Largest Common Vertex on a Rooted TreeFor two nodes in a complete binary tree numbered heap-style, find the deepest common ancestor k and print 10k. | Easy3 | TreeMath+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Router 1Print either a star-shaped router with one internal hub or a fully connected bipartite router, depending on whether N*N exceeds P_lim. | Easy3 | GraphImplementation+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Router 3Build a router with g groups per layer by printing 2Ng directed edges from inputs to internal nodes and from internal nodes to outputs. | Easy3 | GraphImplementation+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Binary treeGiven each node's parent in a binary tree with n up to 20, print the height (distance from the root) of every node. | Easy3 | TreeDFS | No attempts yet | 2s | 512 MB | Judgeable |
| Two-color coloringGiven an undirected multigraph, decide whether it is bipartite so its vertices can be colored with two colors. | Easy3 | GraphBFS+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Misimplemented DinicPrint a fixed 4-vertex, 5-edge flow network; there is no input and the output is a single constant graph. | Easy3 | GraphBrute force+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Election of EvilGiven directed persuasion edges and a set of already-controlled representatives, list the reachable members of target set V in alphabetical order. | Easy3 | GraphBFS+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Prison BreakGiven a grid of '+' and '*' huts where movement is allowed only between huts of the same symbol, decide whether the entry hut can reach the exit hut. | Easy3 | GraphBFS+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Club Room Project (Small)Given N rooms in a row and M wall-breaking actions, count how many rooms remain after all actions merge neighboring rooms. | Easy3 | Union-findImplementation | No attempts yet | 1s | 512 MB | Judgeable |
| Vera and Trail BuildingGiven K, follow a fixed greedy decomposition into complete blocks and print the resulting connected trail network with exactly K two-edge-disjoint paths. | Easy3 | GreedyGraph+2 | No attempts yet | 1s | 512 MB | Judgeable |
| BannerCount connected groups of 1s in an M by N grid where cells touching in any of the eight directions belong to the same group. | Easy3 | GraphDFS+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Tracking Fake NewsModel a story spreading through a social network where each person reposts only if a weighted sum of the story's categories equals their target. | Easy3 | GraphBFS+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Easy Shortest DistanceGiven a grid with one target cell and blocked cells, find the shortest distance from each open cell to the target using 4-directional moves. | Easy3 | BFSGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Paint bucketFlood fill a grid from one pixel, repainting all side-connected pixels sharing the clicked color with a new color, then print the grid. | Easy3 | GraphBFS+2 | No attempts yet | 2s | 512 MB | Judgeable |
| Knight minimum movesGiven two squares on an 8x8 chessboard, output the fewest knight moves needed to get from the first to the second. | Easy3 | BFSGraph+1 | No attempts yet | 2s | 512 MB | Judgeable |
| Xayahh-Rakann at Moloco (Easy)Given n jars and inseparable pairs, decide if exactly k jars can be kept so that no inseparable pair is split across the two groups. | Easy3 | Brute forceGraph+1 | No attempts yet | 2s | 512 MB | Judgeable |
| League of Overwatch at Moloco (Easy)Given a conflict graph, decide whether the vertices can be split into two non-empty groups so every conflicting pair is separated. | Easy3 | GraphBFS | No attempts yet | 2s | 512 MB | Judgeable |
| ExploraceGiven a weighted undirected graph of checkpoints, find the minimum total length of edges that keeps every checkpoint connected. | Easy3 | Minimum spanning treeGraph+2 | No attempts yet | 3s | 512 MB | Judgeable |
| PotionGiven market prices and mixture recipes, compute the cheapest cost to produce one unit of the potion named LOVE. | Medium4 | GraphDynamic programming+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Minimum Spanning TreeCompute the total edge weight of a minimum spanning tree for a weighted undirected graph with up to 10,000 vertices and 100,000 edges, allowing negative weights. | Medium4 | Minimum spanning treeUnion-find+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Distance Between Tree NodesGiven a weighted tree and multiple node pairs, compute the path distance between each pair using tree traversal. | Medium4 | TreeBFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| War - BattleFind connected groups of same-colored soldiers on a grid (4-directional) and output the sum of squared group sizes for each of the two colors. | Medium4 | BFSGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Efficient HackingGiven directed trust edges between N computers, find all computers that, if hacked first, let the hacker reach the maximum possible number of computers. | Medium4 | GraphBFS+1 | No attempts yet | 5s | 256 MB | Judgeable |
| Age RelationsBuild a directed graph from age comparisons and answer queries about who is older using reachability through transitive relations. | Medium4 | GraphDFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Cable DonationGiven an adjacency matrix of cable lengths between rooms encoded as letters, find a minimum spanning tree and output the maximum total cable length that can be donated, or -1 if the rooms cannot all be connected. | Medium4 | Minimum spanning treeGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Tower AttackGiven towers that can relay energy over short hops with 50% loss per hop, compute the maximum damage reachable towers can deal to an enemy using multi-source BFS. | Medium4 | BFSGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Highway ShortcutsCompute the minimum driving distance from position 0 to D on a highway with up to 12 one-way shortcuts that skip forward sections. | Medium4 | Shortest pathGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Police StationsGiven a directed graph and per-city build costs, find strongly connected components and sum the minimum cost city in each component. | Medium4 | GraphDFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Building Completion TimesGiven N buildings with construction times and prerequisite dependencies, compute for each building the earliest possible completion time assuming unlimited parallel construction. | Medium4 | Topological sortDynamic programming+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Downhill PathsCount the number of strictly decreasing height paths from the top-left to the bottom-right cell of a grid, moving only to adjacent cells, using memoized DFS. | Medium4 | Dynamic programmingDFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Sliding PuzzleFind the minimum number of moves to solve a 3x3 sliding puzzle into a fixed goal state, or report -1 if unsolvable. | Medium4 | BFSImplementation+1 | No attempts yet | 1s | 32 MB | Judgeable |
| Length of a Repunit MultipleFind the minimum number of digits in a repunit (a number made only of 1s) that is divisible by a given N, or report -1 if none exists. | Medium4 | MathNumber theory+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Magic Square RotationsGiven four fixed permutations that can be applied to an 8-number arrangement, find the minimum number of operations to reach a target arrangement from the initial one via BFS. | Medium4 | BFSSimulation+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Bipartite GraphFor several undirected graphs, determine whether each one can be 2-colored so that no edge joins two vertices of the same color. | Medium4 | GraphBFS+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Parcel RoutingGiven a weighted graph, compute for every pair of hubs the next hub to visit on a shortest path using all-pairs shortest paths. | Medium4 | Shortest pathGraph+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Painting Board Piece SizesGiven a grid with wall segments blocking movement between adjacent cells, find the largest and smallest connected region sizes using BFS or DFS. | Medium4 | BFSDFS+2 | No attempts yet | 2s | 128 MB | Judgeable |
| Shortest PathCompute single source shortest paths from a given vertex in a directed weighted graph with up to 20,000 vertices and 300,000 edges, printing INF for unreachable vertices. | Medium4 | Shortest pathGraph+1 | No attempts yet | 1s | 256 MB | Judgeable |
| Problem Solving OrderGiven N tasks and M precedence constraints, output a topological order that always picks the smallest available problem number next. | Medium4 | Topological sortHeap+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Different Religions on CampusGiven pairs of students sharing a religion, compute the maximum number of distinct religions possible using union-find over multiple test cases. | Medium4 | Union-findGraph | No attempts yet | 1s | 128 MB | Judgeable |
| WormholesGiven roads with positive weights and wormholes with negative weights, detect whether any negative cycle exists in the resulting directed graph using Bellman-Ford. | Medium4 | Shortest pathGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Ripple EffectValidate a filled Ripple Effect puzzle grid by checking polyomino region digit ranges and minimum-distance spacing rules for repeated numbers in rows and columns. | Medium4 | Union-findSimulation+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Minimum Cost PathGiven a directed weighted graph of cities and bus routes, compute the minimum cost path from a start city to a destination city. | Medium4 | Shortest pathGraph+1 | No attempts yet | 0.5s | 128 MB | Judgeable |
| Network ConnectionGiven N computers and M weighted possible connections, compute the minimum total cost of edges to connect all computers into one network (minimum spanning tree). | Medium4 | Minimum spanning treeUnion-find+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Team AssignmentSplit students into two groups using graph two-coloring so no pair who dislike each other lands on the same team, printing both groups. | Medium4 | GraphBFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Exercise RouteFind the minimum weight cycle in a directed graph with up to 400 vertices, essentially detecting the shortest cycle via all-pairs shortest paths. | Medium4 | Shortest pathGraph+1 | No attempts yet | 2s | 192 MB | Judgeable |
| Diameter of a TreeGiven a weighted tree of up to 10,000 nodes rooted at node 1, compute the maximum-length path between any two nodes. | Medium4 | TreeDFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Minimum Time to Complete TasksGiven tasks with durations and prerequisites forming a DAG (prerequisites always have smaller index), compute the minimum total time to finish all tasks using longest path via DP. | Medium4 | Dynamic programmingTopological sort+1 | No attempts yet | 2s | 256 MB | Judgeable |
| Barn AssignmentGiven each cow's list of acceptable stalls, find the maximum number of cows that can be matched to distinct stalls using bipartite matching. | Medium4 | GraphGreedy | No attempts yet | 2s | 128 MB | Judgeable |
| Number Board JumpCount the distinct length-6 digit strings obtainable by starting anywhere on a 5x5 digit board and making five moves to adjacent cells. | Medium4 | DFSBrute force+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Maximum Independent Set in a TreeGiven a weighted tree, compute a maximum weight independent set using tree DP and output the chosen vertices. | Medium4 | Dynamic programmingTree+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Proving PropositionsGiven directed edges between letters, compute the transitive closure and print all reachable pairs excluding self-loops, sorted by letter order. | Medium4 | GraphDFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Student LineupGiven precedence constraints between N students, output any ordering consistent with all constraints, i.e. a topological sort. | Medium4 | Topological sortGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Building a TreeFind a spanning tree rooted at R that minimizes the sum of parent degrees over all non-root vertices, using a BFS-like greedy shortest path with degree as edge weight. | Medium4 | Shortest pathGraph+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Safe AreasGiven an N x N height grid, find the rain level that maximizes the number of 4-connected regions of unsubmerged cells. | Medium4 | BFSBrute force+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Hamming PathBuild a graph where binary codes connect if their Hamming distance is 1, then output a shortest path between two given codes via BFS. | Medium4 | BFSGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Finding RegionsGiven a grid with several rectangles marked as blocked, find the number of connected empty regions and output their areas sorted ascending. | Medium4 | BFSArray+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Treasure IslandGiven a grid of land and water cells, find the largest shortest-path distance between two connected land cells (grid diameter via multi-source BFS). | Medium4 | BFSGraph+1 | No attempts yet | 1s | 512 MB | Judgeable |
| Meeting PreparationFind connected components in a graph and for each pick the vertex minimizing the eccentricity (graph center). | Medium4 | GraphBFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Music ProgramMerge several partial orderings of singers into one total order using topological sort, or report impossibility if a cycle exists. | Medium4 | Topological sortGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Toy AssemblyCompute how many units of each basic part are needed to build one finished toy given a DAG of assembly quantities. | Medium4 | GraphDFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Selecting NumbersGiven a functional graph i->A_i on 1..N, find the maximum set of indices closed under this mapping (union of cycles) and print it. | Medium4 | GraphArray+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Galaxy MeetingGiven weighted graphs and multiple starting galaxies, find the meeting galaxy that minimizes the sum of squared shortest distances from all participants. | Medium4 | Shortest pathGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| SheepUse flood fill to split a grid into fenced regions, then for each region compare sheep and wolf counts to decide survivors, ignoring regions touching the border. | Medium4 | BFSGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Kkung the ShepherdUsing grid flood-fill to find fenced regions, determine for each region whether sheep or wolves survive by comparing counts, then output totals. | Medium4 | BFSArray+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Breaking CouplesOrient every edge of an undirected graph so each vertex's in-degree and out-degree differ by at most 1, which is always possible via an Euler-tour style pairing on connected components. | Medium4 | GraphDFS+1 | No attempts yet | 2s | 128 MB | Judgeable |
| SearchTrack all reachable cells on a grid as a car moves in given directions by at least one free cell each step, then mark final possible positions. | Medium4 | SimulationArray+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Nearest Common AncestorGiven a rooted tree and two nodes, find their nearest common ancestor for each test case. | Medium4 | TreeDFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Society MembersGiven nested society membership definitions with possible society-name references, compute the total number of distinct human members in the first listed society. | Medium4 | GraphDFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Slim SpanGiven a weighted graph, find the spanning tree that minimizes the difference between its largest and smallest edge weight, or report -1 if disconnected. | Medium4 | Union-findSorting+1 | No attempts yet | 2s | 128 MB | Judgeable |
| Indiana Jones and the Lost Soccer CupGiven precedence constraints between levers, decide whether the order is unique; print the unique order, or report no order or multiple orders. | Medium4 | Topological sortGraph+2 | No attempts yet | 1s | 256 MB | Judgeable |
| Wally WorldTwo points in a plane must meet while a single axis-parallel wall segment blocks the straight path; compute the minimum meeting time. | Medium4 | GeometryMath+2 | No attempts yet | 1s | 128 MB | Judgeable |
| CountdownGiven one family tree per test case, count for each person how many descendants sit exactly d generations below, then rank the top holders. | Medium4 | GraphDFS+1 | No attempts yet | 1s | 128 MB | Judgeable |
| Dominos 2Given directed edges between dominos and a set of manually pushed dominos, count how many dominos end up falling. | Medium4 | GraphDFS+2 | No attempts yet | 1s | 128 MB | Judgeable |
| DominosGiven a directed graph of domino toppling relations, find the minimum number of blocks to push by hand so that all blocks fall. | Medium4 | GraphDFS+1 | No attempts yet | 1s | 256 MB | Judgeable |
| TreeGiven the preorder and inorder traversals of a binary tree, reconstruct the tree and print its postorder traversal. | Medium4 | TreeRecursion+1 | No attempts yet | 1s | 192 MB | Judgeable |
| SubwayFind the shortest travel time from home to school using walking and subway lines, rounding the answer to the nearest minute. | Medium4 | Shortest pathGraph+2 | No attempts yet | 1s | 128 MB | Judgeable |
| The Status is Not QuoGiven circuit board squares with wired connection points, trace each exterior start point to the exterior point where its wire path ends. | Medium4 | SimulationGraph+1 | No attempts yet | 1s | 128 MB | Judgeable |