// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
// A recursive helper does the walking; it closes over visited and order.
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
// A recursive helper does the walking; it closes over visited and order.
var visit func(node int)
visit = func(node int) {
}
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
// A recursive helper does the walking; it closes over visited and order.
var visit func(node int)
visit = func(node int) {
// Mark this node the moment we arrive, and record the visit.
}
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
// A recursive helper does the walking; it closes over visited and order.
var visit func(node int)
visit = func(node int) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true
order = append(order, node)
}
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
// A recursive helper does the walking; it closes over visited and order.
var visit func(node int)
visit = func(node int) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true
order = append(order, node)
// Dive into each unvisited neighbor before returning ("depth first").
}
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
// A recursive helper does the walking; it closes over visited and order.
var visit func(node int)
visit = func(node int) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true
order = append(order, node)
// Dive into each unvisited neighbor before returning ("depth first").
for _, next := range graph[node] {
if !visited[next] {
visit(next)
}
}
}
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
// A recursive helper does the walking; it closes over visited and order.
var visit func(node int)
visit = func(node int) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true
order = append(order, node)
// Dive into each unvisited neighbor before returning ("depth first").
for _, next := range graph[node] {
if !visited[next] {
visit(next)
}
}
}
// Kick off the traversal from the start node.
}// graph is an adjacency list: graph[node] = list of neighbors.
func dfs(graph [][]int, start int) []int {
// visited stops us from revisiting nodes (and looping forever on cycles).
visited := make([]bool, len(graph))
order := []int{}
// A recursive helper does the walking; it closes over visited and order.
var visit func(node int)
visit = func(node int) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true
order = append(order, node)
// Dive into each unvisited neighbor before returning ("depth first").
for _, next := range graph[node] {
if !visited[next] {
visit(next)
}
}
}
// Kick off the traversal from the start node.
visit(start)
return order // O(V + E)
}# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
pass# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []
# A nested helper does the walking; it closes over visited and order.# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []
# A nested helper does the walking; it closes over visited and order.
def visit(node):
pass# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []
# A nested helper does the walking; it closes over visited and order.
def visit(node):
# Mark this node the moment we arrive, and record the visit.# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []
# A nested helper does the walking; it closes over visited and order.
def visit(node):
# Mark this node the moment we arrive, and record the visit.
visited[node] = True
order.append(node)# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []
# A nested helper does the walking; it closes over visited and order.
def visit(node):
# Mark this node the moment we arrive, and record the visit.
visited[node] = True
order.append(node)
# Dive into each unvisited neighbor before returning ("depth first").# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []
# A nested helper does the walking; it closes over visited and order.
def visit(node):
# Mark this node the moment we arrive, and record the visit.
visited[node] = True
order.append(node)
# Dive into each unvisited neighbor before returning ("depth first").
for nxt in graph[node]:
if not visited[nxt]:
visit(nxt)# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []
# A nested helper does the walking; it closes over visited and order.
def visit(node):
# Mark this node the moment we arrive, and record the visit.
visited[node] = True
order.append(node)
# Dive into each unvisited neighbor before returning ("depth first").
for nxt in graph[node]:
if not visited[nxt]:
visit(nxt)
# Kick off the traversal from the start node.# graph is an adjacency list: graph[node] = list of neighbors.
def dfs(graph, start):
# visited stops us from revisiting nodes (and looping forever on cycles).
visited = [False] * len(graph)
order = []
# A nested helper does the walking; it closes over visited and order.
def visit(node):
# Mark this node the moment we arrive, and record the visit.
visited[node] = True
order.append(node)
# Dive into each unvisited neighbor before returning ("depth first").
for nxt in graph[node]:
if not visited[nxt]:
visit(nxt)
# Kick off the traversal from the start node.
visit(start)
return order # O(V + E)// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
// A nested helper does the walking; it closes over visited and order.
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node) {
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node) {
// Mark this node the moment we arrive, and record the visit.
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
// Dive into each unvisited neighbor before returning ("depth first").
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (const next of graph[node]) {
if (!visited[next]) visit(next);
}
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (const next of graph[node]) {
if (!visited[next]) visit(next);
}
}
// Kick off the traversal from the start node.
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph, start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited = new Array(graph.length).fill(false);
const order = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (const next of graph[node]) {
if (!visited[next]) visit(next);
}
}
// Kick off the traversal from the start node.
visit(start);
return order; // O(V + E)
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
// A nested helper does the walking; it closes over visited and order.
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node: number): void {
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node: number): void {
// Mark this node the moment we arrive, and record the visit.
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node: number): void {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node: number): void {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
// Dive into each unvisited neighbor before returning ("depth first").
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node: number): void {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (const next of graph[node]) {
if (!visited[next]) visit(next);
}
}
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node: number): void {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (const next of graph[node]) {
if (!visited[next]) visit(next);
}
}
// Kick off the traversal from the start node.
}// graph is an adjacency list: graph[node] = list of neighbors.
function dfs(graph: number[][], start: number): number[] {
// visited stops us from revisiting nodes (and looping forever on cycles).
const visited: boolean[] = new Array(graph.length).fill(false);
const order: number[] = [];
// A nested helper does the walking; it closes over visited and order.
function visit(node: number): void {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (const next of graph[node]) {
if (!visited[next]) visit(next);
}
}
// Kick off the traversal from the start node.
visit(start);
return order; // O(V + E)
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
}
// A helper does the walking; Java has no closures over locals, so the
// visited set and the output list are passed down explicitly.
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
}
// A helper does the walking; Java has no closures over locals, so the
// visited set and the output list are passed down explicitly.
private void visit(List<List<Integer>> graph, int node,
boolean[] visited, List<Integer> order) {
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
}
// A helper does the walking; Java has no closures over locals, so the
// visited set and the output list are passed down explicitly.
private void visit(List<List<Integer>> graph, int node,
boolean[] visited, List<Integer> order) {
// Mark this node the moment we arrive, and record the visit.
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
}
// A helper does the walking; Java has no closures over locals, so the
// visited set and the output list are passed down explicitly.
private void visit(List<List<Integer>> graph, int node,
boolean[] visited, List<Integer> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.add(node);
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
}
// A helper does the walking; Java has no closures over locals, so the
// visited set and the output list are passed down explicitly.
private void visit(List<List<Integer>> graph, int node,
boolean[] visited, List<Integer> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.add(node);
// Dive into each unvisited neighbor before returning ("depth first").
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
}
// A helper does the walking; Java has no closures over locals, so the
// visited set and the output list are passed down explicitly.
private void visit(List<List<Integer>> graph, int node,
boolean[] visited, List<Integer> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.add(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (int next : graph.get(node)) {
if (!visited[next]) {
visit(graph, next, visited, order);
}
}
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
// Kick off the traversal from the start node.
}
// A helper does the walking; Java has no closures over locals, so the
// visited set and the output list are passed down explicitly.
private void visit(List<List<Integer>> graph, int node,
boolean[] visited, List<Integer> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.add(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (int next : graph.get(node)) {
if (!visited[next]) {
visit(graph, next, visited, order);
}
}
}
}import java.util.ArrayList;
import java.util.List;
class Solution {
// graph is an adjacency list: graph.get(node) = list of neighbors.
public List<Integer> dfs(List<List<Integer>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
boolean[] visited = new boolean[graph.size()];
List<Integer> order = new ArrayList<>();
// Kick off the traversal from the start node.
visit(graph, start, visited, order);
return order; // O(V + E)
}
// A helper does the walking; Java has no closures over locals, so the
// visited set and the output list are passed down explicitly.
private void visit(List<List<Integer>> graph, int node,
boolean[] visited, List<Integer> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.add(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (int next : graph.get(node)) {
if (!visited[next]) {
visit(graph, next, visited, order);
}
}
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
}
// A helper does the walking; visited and order are passed down so the
// recursion carries no state of its own.
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
}
// A helper does the walking; visited and order are passed down so the
// recursion carries no state of its own.
private void Visit(IList<IList<int>> graph, int node,
bool[] visited, List<int> order) {
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
}
// A helper does the walking; visited and order are passed down so the
// recursion carries no state of its own.
private void Visit(IList<IList<int>> graph, int node,
bool[] visited, List<int> order) {
// Mark this node the moment we arrive, and record the visit.
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
}
// A helper does the walking; visited and order are passed down so the
// recursion carries no state of its own.
private void Visit(IList<IList<int>> graph, int node,
bool[] visited, List<int> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.Add(node);
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
}
// A helper does the walking; visited and order are passed down so the
// recursion carries no state of its own.
private void Visit(IList<IList<int>> graph, int node,
bool[] visited, List<int> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.Add(node);
// Dive into each unvisited neighbor before returning ("depth first").
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
}
// A helper does the walking; visited and order are passed down so the
// recursion carries no state of its own.
private void Visit(IList<IList<int>> graph, int node,
bool[] visited, List<int> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.Add(node);
// Dive into each unvisited neighbor before returning ("depth first").
foreach (int next in graph[node]) {
if (!visited[next]) {
Visit(graph, next, visited, order);
}
}
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
// Kick off the traversal from the start node.
}
// A helper does the walking; visited and order are passed down so the
// recursion carries no state of its own.
private void Visit(IList<IList<int>> graph, int node,
bool[] visited, List<int> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.Add(node);
// Dive into each unvisited neighbor before returning ("depth first").
foreach (int next in graph[node]) {
if (!visited[next]) {
Visit(graph, next, visited, order);
}
}
}
}using System.Collections.Generic;
public class Solution {
// graph is an adjacency list: graph[node] = list of neighbors.
public IList<int> Dfs(IList<IList<int>> graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool[] visited = new bool[graph.Count];
List<int> order = new List<int>();
// Kick off the traversal from the start node.
Visit(graph, start, visited, order);
return order; // O(V + E)
}
// A helper does the walking; visited and order are passed down so the
// recursion carries no state of its own.
private void Visit(IList<IList<int>> graph, int node,
bool[] visited, List<int> order) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.Add(node);
// Dive into each unvisited neighbor before returning ("depth first").
foreach (int next in graph[node]) {
if (!visited[next]) {
Visit(graph, next, visited, order);
}
}
}
}#include <stdbool.h>
#include <stdlib.h>
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
}#include <stdbool.h>
#include <stdlib.h>
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
}#include <stdbool.h>
#include <stdlib.h>
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
}#include <stdbool.h>
#include <stdlib.h>
// Declared up front so dfs can call it before it is defined below.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node);
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
}#include <stdbool.h>
#include <stdlib.h>
// Declared up front so dfs can call it before it is defined below.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node);
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
}
// The recursive helper. C has no closures, so every piece of state travels
// in the parameter list.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node) {
}#include <stdbool.h>
#include <stdlib.h>
// Declared up front so dfs can call it before it is defined below.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node);
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
}
// The recursive helper. C has no closures, so every piece of state travels
// in the parameter list.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node) {
// Mark this node the moment we arrive, and record the visit.
}#include <stdbool.h>
#include <stdlib.h>
// Declared up front so dfs can call it before it is defined below.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node);
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
}
// The recursive helper. C has no closures, so every piece of state travels
// in the parameter list.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order[(*count)++] = node;
}#include <stdbool.h>
#include <stdlib.h>
// Declared up front so dfs can call it before it is defined below.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node);
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
}
// The recursive helper. C has no closures, so every piece of state travels
// in the parameter list.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order[(*count)++] = node;
// Dive into each unvisited neighbor before returning ("depth first").
}#include <stdbool.h>
#include <stdlib.h>
// Declared up front so dfs can call it before it is defined below.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node);
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
}
// The recursive helper. C has no closures, so every piece of state travels
// in the parameter list.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order[(*count)++] = node;
// Dive into each unvisited neighbor before returning ("depth first").
for (int i = 0; i < colSizes[node]; i++) {
int next = graph[node][i];
if (!visited[next]) {
visit(graph, colSizes, visited, order, count, next);
}
}
}#include <stdbool.h>
#include <stdlib.h>
// Declared up front so dfs can call it before it is defined below.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node);
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
// Kick off the traversal from the start node.
}
// The recursive helper. C has no closures, so every piece of state travels
// in the parameter list.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order[(*count)++] = node;
// Dive into each unvisited neighbor before returning ("depth first").
for (int i = 0; i < colSizes[node]; i++) {
int next = graph[node][i];
if (!visited[next]) {
visit(graph, colSizes, visited, order, count, next);
}
}
}#include <stdbool.h>
#include <stdlib.h>
// Declared up front so dfs can call it before it is defined below.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node);
// graph is an adjacency list: graph[node] holds colSizes[node] neighbors.
int* dfs(int** graph, int graphSize, int* colSizes, int start, int* returnSize) {
// visited stops us from revisiting nodes (and looping forever on cycles).
bool* visited = calloc(graphSize, sizeof(bool));
int* order = malloc(graphSize * sizeof(int));
int count = 0;
// Kick off the traversal from the start node.
visit(graph, colSizes, visited, order, &count, start);
free(visited);
*returnSize = count;
return order; // caller owns the buffer. O(V + E)
}
// The recursive helper. C has no closures, so every piece of state travels
// in the parameter list.
static void visit(int** graph, int* colSizes, bool* visited,
int* order, int* count, int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order[(*count)++] = node;
// Dive into each unvisited neighbor before returning ("depth first").
for (int i = 0; i < colSizes[node]; i++) {
int next = graph[node][i];
if (!visited[next]) {
visit(graph, colSizes, visited, order, count, next);
}
}
}#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
// A recursive lambda does the walking. std::function is what lets it
// name itself; [&] captures visited and order by reference.
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
// A recursive lambda does the walking. std::function is what lets it
// name itself; [&] captures visited and order by reference.
function<void(int)> visit = [&](int node) {
};
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
// A recursive lambda does the walking. std::function is what lets it
// name itself; [&] captures visited and order by reference.
function<void(int)> visit = [&](int node) {
// Mark this node the moment we arrive, and record the visit.
};
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
// A recursive lambda does the walking. std::function is what lets it
// name itself; [&] captures visited and order by reference.
function<void(int)> visit = [&](int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push_back(node);
};
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
// A recursive lambda does the walking. std::function is what lets it
// name itself; [&] captures visited and order by reference.
function<void(int)> visit = [&](int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push_back(node);
// Dive into each unvisited neighbor before returning ("depth first").
};
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
// A recursive lambda does the walking. std::function is what lets it
// name itself; [&] captures visited and order by reference.
function<void(int)> visit = [&](int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push_back(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (int next : graph[node]) {
if (!visited[next]) {
visit(next);
}
}
};
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
// A recursive lambda does the walking. std::function is what lets it
// name itself; [&] captures visited and order by reference.
function<void(int)> visit = [&](int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push_back(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (int next : graph[node]) {
if (!visited[next]) {
visit(next);
}
}
};
// Kick off the traversal from the start node.
}
};#include <functional>
#include <vector>
using namespace std;
class Solution {
public:
// graph is an adjacency list: graph[node] = list of neighbors.
vector<int> dfs(vector<vector<int>>& graph, int start) {
// visited stops us from revisiting nodes (and looping forever on cycles).
vector<bool> visited(graph.size(), false);
vector<int> order;
// A recursive lambda does the walking. std::function is what lets it
// name itself; [&] captures visited and order by reference.
function<void(int)> visit = [&](int node) {
// Mark this node the moment we arrive, and record the visit.
visited[node] = true;
order.push_back(node);
// Dive into each unvisited neighbor before returning ("depth first").
for (int next : graph[node]) {
if (!visited[next]) {
visit(next);
}
}
};
// Kick off the traversal from the start node.
visit(start);
return order; // O(V + E)
}
};Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.