graph dfs traversal Pattern

Clone Graph

Clone Graph involves cloning a graph using DFS, focusing on graph traversal and neighbor management using hash tables.

Reconstruct Itinerary

Reconstruct Itinerary requires building a valid travel route using all tickets once, starting from JFK with lexical orde…

Evaluate Division

Compute the results of division queries from given equations using graph traversal and depth-first search efficiently.

Number of Provinces

Solve Number of Provinces by scanning the adjacency matrix and launching DFS once per unvisited city component.

Redundant Connection

Identify and remove the redundant edge that causes a cycle in a graph starting as a tree.

Redundant Connection II

Find and remove the redundant connection in a directed graph that was originally a rooted tree.

Network Delay Time

Find the minimum time for a signal to travel to all nodes in a directed graph or determine if it's impossible.

Cracking the Safe

The Cracking the Safe problem involves finding the shortest password sequence to unlock a safe using graph traversal and…

Couples Holding Hands

This problem requires arranging couples sitting apart in a row with the minimum number of swaps using graph traversal an…

Is Graph Bipartite?

Determine whether an undirected graph can be split into two independent sets using DFS, BFS, or Union Find patterns.

Cheapest Flights Within K Stops

Find the cheapest flight from a source to a destination with at most K stops using graph traversal techniques efficientl…

All Paths From Source to Target

Find all paths in a directed acyclic graph (DAG) from source to target using depth-first search and backtracking.

Sum of Distances in Tree

The problem asks to compute the sum of distances between each node and all others in a tree structure using depth-first …

Keys and Rooms

Determine if all rooms can be visited given keys distributed across a set of interconnected locked rooms using graph tra…

Possible Bipartition

Determine if a group of n people with mutual dislikes can be split into two non-conflicting groups using graph traversal…

Most Stones Removed with Same Row or Column

Maximize the number of stones removed from a 2D plane using graph traversal and DFS.

Flower Planting With No Adjacent

In this problem, you are tasked with planting flowers in gardens with specific constraints based on graph traversal prin…

Critical Connections in a Network

Find critical connections in a network of servers, ensuring efficient traversal using depth-first search and Tarjan's al…

Number of Operations to Make Network Connected

Determine the minimum number of operations required to connect all computers in a network with a limited number of cable…

Validate Binary Tree Nodes

Validate Binary Tree Nodes problem requires checking if a set of nodes forms a valid binary tree using graph traversal.

Frog Position After T Seconds

The problem asks for the probability that a frog reaches a target vertex after t seconds in a tree graph.

Reorder Routes to Make All Paths Lead to the City Zero

Reorder Routes to Make All Paths Lead to the City Zero involves reversing the direction of roads in a tree to ensure all…

Find if Path Exists in Graph

Determine if a valid path exists between two vertices in a bi-directional graph using traversal techniques.

Find All People With Secret

Find all people who receive a secret through meetings using graph traversal with depth-first search efficiently and corr…

Valid Arrangement of Pairs

Given pairs of numbers, find a valid arrangement where each pair follows a specific condition.

Detonate the Maximum Bombs

Determine the maximum number of bombs that can be detonated by leveraging chain reactions using graph traversal and DFS …

Count Unreachable Pairs of Nodes in an Undirected Graph

Calculate the total number of node pairs in an undirected graph that cannot reach each other using DFS, BFS, or Union Fi…

Find Closest Node to Given Two Nodes

Find the node that minimizes the maximum distance to two given nodes in a directed graph with one outgoing edge per node…

Most Profitable Path in a Tree

Solve the 'Most Profitable Path in a Tree' problem using graph traversal and depth-first search techniques to maximize A…

Minimum Fuel Cost to Report to the Capital

Calculate the minimum fuel needed for all city representatives to reach the capital using DFS on a tree graph efficientl…

Minimum Score of a Path Between Two Cities

Find the minimum distance in a path connecting two cities using graph traversal strategies efficiently.

Divide Nodes Into the Maximum Number of Groups

Determine the maximum number of groups nodes can form in a graph using depth-first traversal without violating edge conn…

Minimize the Total Price of the Trips

Calculate the minimum total cost of multiple trips on a tree by selectively halving node prices using DFS frequency coun…

Count the Number of Complete Components

Determine the number of complete connected components in an undirected graph using efficient traversal techniques and gr…

Minimum Edge Reversals So Every Node Is Reachable

This problem requires solving a graph traversal with edge reversals to ensure every node is reachable in a tree-like str…

Find Edges in Shortest Paths

Use two Dijkstra runs to mark exactly which edges can appear on at least one shortest path from 0 to n - 1.

Find Minimum Diameter After Merging Two Trees

Calculate the minimum diameter after merging two trees by strategically connecting nodes to minimize the longest path in…

Time Taken to Mark All Nodes

Calculate the time taken to mark all nodes in a tree, starting from any node with time t=0.

Remove Methods From Project

Remove suspicious methods in a project that are invoked directly or indirectly from a buggy method using graph traversal…

Maximize Amount After Two Days of Conversions

Compute the maximum currency amount after two days using graph traversal and depth-first search for optimal conversions.

Minimize the Maximum Edge Weight of Graph

Minimize the maximum edge weight in a graph after removing certain edges while ensuring node reachability.

Unit Conversion I

Solve the unit conversion problem by using graph traversal to compute equivalent unit amounts.

Maximum Sum of Edge Values in a Graph

Maximize the sum of edge values in a connected graph by assigning unique node values and optimizing edge products.