LeetCode Notes

Basic Data Structures

Logic categories
1. Linear: array, stack, queue, linked list
2. Non-linear: tree, graph
Linear
1. array: the most basic one
2. queue: FIFO, enqueue from back, dequeue from head
3. stack: LIFO, push from head, pop from head, peed from head
4. linked list

Non-linear

tree: DOM, XML
1. a tree is a acyclic connected graph
2. tree is recursive
binary tree
1. degree of a node is at most 2
2. all trees can be represented by binary trees
3. heap
  1. a heap is a priority queue
  2. binary heap
    1. definition:
      - heap property: each node is smaller (min heap) or larger (max heap) than its children
      - the left subtree and right subtree of each node is a binary heap
4. binary search tree
  1. definition
    - each node on left subtree is smaller than root node
    - each node on right subtree is larger than root node
    - the left subtree and right subtree of each node is a binary search tree
  2. the traversal result of a binary search tree is sorted
5. balanced binary tree
  1. AVL
  2. RBT
6. Trie tree
graph
1. directed/undirected, weighted/unweighted, cyclic/acyclic, in-degree/out-degree, path/cycle, connected(undirected)/strong connected(directed)
2. spanning tree: a tree with n nodes and n - 1 edges
  1. MST: minimum possible total edge weight
3. construct a graph
  1. adjacent matrix
  2. adjacent list
4. graph traversal
  1. if theres is cycle in a tree, you need to store which nodes have been visited
  2. DFS
  3. BFS

graph algorithm

dijkstra

shortest path, it' greedy algorithm (find shortest neighbor), it's dfs

time complexity: \(O(logN)\)

import heapq

def dijkstra(graph, start, end) {
   heap = [(0, start)]
   visited = set()
   while heap:
      cost, node = heapq.heappop(heap)
      if node in visited:
         continue
      visited.add(node)
      if node == end:
         return cost
      for nbr, w in graph.adjacent(node):
         if nbr in visited:
            continue
         cur_cost = cost + w
         heapq.heappush(heap, (cur_cost, nbr))
   return -1
}

floyd-warshall

can be used to calculate dist between arbitrage two points because it save the intermediate results, while dijkstra only solves shortest path from singe start, you need a loop to solve multiple-source shortest path problem in dijkstra
it used dynamic programming rather than greedy, to it can handles negative weights

time complexity: \(O(n^3)\), space complexity: \(O(n^2)\)

# let graph[i][j] is the adjacent matrix of graph G

def floyd(graph, n):
   dist = [[float("inf") for _ in range(n)] for _ in range(n)]
   for i in range(n):
      for j in range(n):
         dist[i][j] = graph[i][j]
   # The outmost layer should be k
   for k in range(n):
      for i in range(n):
         for j in range(n):
            if dist[i][k] != float("inf") and dist[k][j] != float("inf") and dist[i][j] > dist[i][k] + dist[k][j]:
               dist[i][j] = dist[i][k] + dist[k][j]
   return dist

bellman-ford

can solve single source shortest path problem

based on dynamic programming, it's slower thant dijkstra algorithm, but it can handle negative weights

# let edges be a list of edges, each edge is a list [u, v, w] where u and v are vertices, and w is the weight of edge uv
# n is the number of vertices
def bellman(edges, start, n):
   dist = [float("inf") for _ in range(n)]:
   dist[start] = 0
   for _ in range(n):
      for u, v, w in edges:
         if dist[u] != float("inf") and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
   # check if there is a negative weight cycle
   for u, v, w in edges:
      if dist[u] != float("inf") and dist[u] + w < dist[v]:
         return None
   return dist

topological sort

topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering
a topological sort is possible if and only if the graph has not directed cycles, that is, if it is a directed acyclic graph(DAG), and any DAG has at least on topological ordering

Kahn algorithm

processes:
- compute in-degree of each vertex, and initialize visited vertices amount to 0
- put all vertices with in-degree 0 into a queue
- remove a vertex from the queue and then increase visited vertices amount by one, decrease in-degree of its adjacent vertices by one, if in-degree of a neighboring vertex is reduced to 0, add it to the queue, and repeat this process until the queue is empty
- if the visited vertices amount is not equal to the total amount of vertices, there is a cycle in the graph, otherwise the done

time complexity: \(O(V + E)\)

def kahn(graph):
   indegree = [0] * len(graph.V)
   queue = collections.deque()
   res = []
   cnt = 0
   for u,v in graph.E:
      indegree[v] += 1
   for i in range(len(graph.V)):
      if indegree[i] == 0:
         queue.append(i)
   while queue:
      cur = queue.popleft()
      res.append(cur)
      cnt += 1
      for nbr in graph.adjacent(cur):
         indegree[nbr] -= 1
         if indegree[nbr] == 0:
            queue.append(nbr)
   if cnt != len(graph.V):
      return None
   return res

minimum spanning tree

a minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weigh
spanning tree and MST may not be unique

Kruskal algorithm

processes:
- create a forest F (a set of trees), where each vertex in the graph is a separate tree
- create a set S containing all the edges in the graph
- while S is nonempty and F is not yet spanning, remove an edge with minimum weight from S, if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree

time complexity: \(O(ElogE)\)

# This class is for union find
class DisjointSetUnion:
   def __init__(self, n):
      self.n = n
      self.rank = [1] * n
      self.f = list(range(n))
   
   def find(self, x: int) -> int:
      if self.f[x] == x:
            return x
      self.f[x] = self.find(self.f[x])
      return self.f[x]
   
   def unionSet(self, x: int, y: int) -> bool:
      fx, fy = self.find(x), self.find(y)
      if fx == fy:
            return False
      if self.rank[fx] < self.rank[fy]:
            fx, fy = fy, fx
      self.rank[fx] += self.rank[fy]
      self.f[fy] = fx
      return True

class Algorithm:
   def Kruskal(self, graph):
      dsu = DisjointSetUnion(len(graph.V))
      graph.E.sort()
      ret, num = 0, 1
      for u, v, w in graph.E:
            if dsu.unionSet(u, v):
               ret += w
               num += 1
               if num == n:
                  break
      return ret

Prim algorithm

processes:
- initialize a tree with a single vertex, chosen arbitrarily from the graph
- grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree
- repeat the above step until all vertices are in the tree

time complexity: \(O(E + VlogV)\)

class Solution:
   def Prim(self, dist) -> int:
      n = len(dist)
      d = [float("inf")] * n
      vis = [False]  * n
      d[0] = 0
      ans = 0
      for _ in range(n):
            M = float("inf") 
            for i in range(n):
               if not vis[i] and d[i] < M:
                  node = i
                  M = d[i]
            vis[node] = True
            ans += M
            for i in range(n):
               if not vis[i]:
                  d[i] = min(d[i], dist[i][node])
      return ans

LinkedList

It's helpful to use a dummy node to simplify your code with linked list

Template

Binary search, time complexity O(logN)

private int binarySearchHelper(int[] nums, target, low, high) {
   if (low > high) {
      return -1;
   }
   int mid = low + (high - low ) / 2;
   if (nums[mid] == target) {
      return mid;
   } else if (nums[mid] < target ) {
      return binarySearchHelper(nums, target, mid + 1, high);
   } else {
      return binarySearchHelper(nums, target, low, mid - 1);
   }
}

public int binarySearch(int[] nums, int target) {
   return binarySearchHelper(nums, target, 0, nums.length - 1);
}

Binary Tree traversal

PreOrder, time complexity: O(N)

// Recursive
public void preOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   System.out.println(root.data);
   preOrder(root.left);
   preOrder(root.right);

}

// Iterative, space complexity: O(N)
public void preOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   Stack<TreeNode> stack = new Stack<>();
   stack.push(root);
   while (!stack.isEmpty()) {
      TreeNode cur = stack.pop();
      System.out.println(cur.data);
      if (cur.right != null) {
         stack.push(cur.right);
      }
      if (cur.left != null) {
         stack.push(cur.left);
      }
   }

}

// Morris traversal, space complexity: O(1)
public void preOrder(TreeNode root) {
   TreeNode cur = root;
   while (cur != null) {
      if (cur.left == null) {
         System.out.println(cur.data);
         cur = cur.right;
      } else {
         TreeNode pre = cur.left;
         while (pre.right != null && pre.right != cur) {
            pre = pre.right;
         }
         if (pre.right == null) {
            System.out.println(cur.data);
            pre.right = cur;
            cur = cur.left;
         } else {
            pre.right = null;
            cur = cur.right;     
         }
      }
   }
}

InOrder, time complexity: O(N)

// Recursive
public void inOrder(TreeNode root) {
   if (root == null) {
      return;
   } 
   inOrder(root.left);
   System.out.println(root.data);
   inOrder(root.right);
}

// Iterative, space complexity: O(N)
public void inOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   Stack<TreeNode> stack = new Stack<>();
   TreeNode cur = root;
   while (cur != null || !stack.isEmpty()) {
      while (cur != null) {
         stack.push(cur);
         cur = cur.left;
      }
      cur = stack.pop();
      System.out.println(cur.data);
      cur = cur.right;
   }
}

// Morris traversal, space complexity: O(1)
public void inOrder(TreeNode root) {
   TreeNode cur = root;
   while (cur != null) {
      if (cur.left == null) {
         System.out.println(cur.data);
         cur = cur.right;
      } else {
         // find the predecessor of cur
         TreeNode pre = cur.left;
         while (pre.right != null && pre.right != cur) {
            pre = pre.right;
         }
         if (pre.right == null) {
            // If we haven't visited the predecessor before, add a link
            // so we can come back to cur
            pre.right = cur;
            cur = cur.left;
         } else {
            // If we have visited the predecessor before, then the
            // left-subtree of cur has been traversed, so we can
            // safely remove the link and print cur's data 
            pre.right = null;
            System.out.println(cur.data);
            cur = cur.right;
         }
      }
   }
}

PostOrder, time complexity: O(N)

// Recursive
public void postOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   postOrder(root.left);
   postOrder(root.right);
   System.out.println(root.data);
}

// Iterative
public void postOrder(TreeNode root) {
   TreeNode cur = root;
   TreeNode pre = null;
   Stack<TreeNode> stack = new Stack<>();      
   while(cur != null || !stack.empty()){
      while (cur != null){				
         stack.push(cur);
         cur = cur.left;
      }
      cur = stack.peek();
      if(cur.right == null || cur.right == pre){
         // If no right subtree or we have visited the right subtree
         System.out.println(cur.data);
         stack.pop();
         pre = cur;
         cur = null;
      }
      else
         // Visit the right subtree
         cur = cur.right;
   }
}

LevelOrder, time complexity: O(N)

// Iterative
public void levelOrder(TreeNode root) {
   if (root == null) {
      return;
   }
   Queue<TreeNode> queue = new LinkedList<>();
   queue.add(root);
   while (!queue.isEmpty()) {
      TreeNode cur = queue.poll();
      System.out.println(cur.data);
      if (cur.left != null) {
         queue.add(cur.left);
      }
      if (cur.right != null) {
         queue.add(cur.right);
      }
   }
}

Height, time complexity: O(N)

Height of a node: the number of edges on the longest path from the node to a leaf

public int height(TreeNode root) {
   if (root == null) {
      return -1;
   }
   return Math.max(height(root.left), height(root.right)) + 1;
}

Binary, time complexity: O(N)

Depth of a node: the number of edges on the path from the node to the root

public int depth(TreeNode root, TreeNode node) {
   if (root == node) {
      return 0;
   }
   return 1 + depth(root, node.parent);
}

BST

Search, time complexity: on average O(H)

public TreeNode search(TreeNode root, int data) {
   if (root == null || root.data == data) {
      return root;
   }
   if (root.data > data) {
      return search(root.left, data);
   }
   if (root.data < data) {
      return search(root.right, data);
   }
}

Minimum/Maximum time complexity: on average O(H)

public TreeNode minimum(TreeNode root) {
   TreeNode cur = root;
   while (cur.left != null) {
      cur = cur.left;
   }
   return cur;
}

public TreeNode maximum(TreeNode root) {
   TreeNode cur = root;
   while (cur.right != null) {
      cur = cur.right;
   }
   return cur;
}

Successor/Predecessor, time complexity: on average O(H)

public TreeNode successor(TreeNode node) {
   if (node.right != null) {
      return minimum(node.right);
   }
   TreeNode cur = node;
   while (cur.parent != null && cur == cur.parent.right) {
      cur = cur.parent;
   }
   return cur.parent;
}

public TreeNode predecessor(TreeNode node) {
   if (node.left != null) {
      return maximum(node.left);
   }
   TreeNode cur = node;
   while (cur.parent != null && cur == cur.parent.left) {
      cur = cur.parent;
   }
   return cur.parent;
}

Insert, time complexity: on average O(H)

// Iterative
public TreeNode insert(TreeNode root, TreeNode node) {
   TreeNode prev = null;   // prev is the parent of the inserted node
   TreeNode cur = root;   // cur is where node should be inserted
   while (cur != null) {
      prev = cur;
      if (cur.data > node.data) {
         cur = cur.left;
      } else {
         cur = cur.right;
      }
   }
   node.parent = prev;
   if (prev == null) {  // root is null, empty tree
      root = node;
   } else {
      if (prev.data > node.data) {
         prev.left = node;
      } else {
         prev.right = node;
      }
   }
   return root;
}

// Recursive
public TreeNode insert(TreeNode root, TreeNode node) {
   if (root == null) {
      root = node;
      return root;
   }
   if (root.data > node.data) {
      TreeNode left = insert(root.left, node);
      root.left = left;
      left.parent  = root;
   } else if (root.data < node.data) {
      TreeNode right = insert(root.right, node);
      root.right = right;
      right.parent = root;
   }
   return root;
}

Delete, time complexity: on average O(H)

// Iterative
public TreeNode delete(TreeNode root, TreeNode node) {
   TreeNode replace = null;
   if (node.left == null ||node.right == null) {
      replace = node;
   } else {
      replace = successor(node); 
   }
   // If replace is node, then child is the child of node or null, the following 
   // code delete node, connect parent of node and child
   // If replace is not node, then child is the child of successor of node,
   // the following code delete successor, connect its parent and child 
   TreeNode child = null;
   if (replace.left == null) {
      child = replace.right;
   } else {
      child = replace.left;
   }
   if (child != null) {
      child.parent = replace.parent;
   }
   if (replace.parent == null) {
      root = child;
   } else {
      if (replace.equals(replace.parent.left)) {
         replace.parent.left = child;
      } else {
         replace.parent.right = child;
      }
   }
   if (!replace.equals(node)) {
      node.data = replace.data;
   }
   return root;
}

// Recursive
public TreeNode delete (TreeNode root, TreeNode node) {
   if (root == null) {
      return null;
   }
   if (root.data < node.data) {
      TreeNode right = delete(root.right, node);
      root.right = right;
      if (right != null) {
         right.parent = root;
      }
   } else if (root.data > node.data) {
      TreeNode left = delete(root.left, node);
      root.left = left;
      if (left != null) {
         left.parent = root;
      }
   } else {
      if (root.left == null) {
         return root.right;
      } else if (root.right == null) {
         return root.left;
      }
      TreeNode successor = minimum(root.right);
      root.data = successor.data;
      root.right = delete(root.right, successor);
   }
   return root;
}

Sorting

Bubble sorting, time complexity: O(N^2)

public void bubbleSort(int[] arr) {
   int n = arr.length;
   for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
         if (arr[j] > arr[j + 1]) {
            int tmp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = tmp;
         }
      }
   }
}

public void bubbleSort(int[] a) {
   boolean disSwap = true;
   while (disSwap) {
      disSwap = false;
      for (int i = 0; i < a.length - 1; i++) {
         if (a[i] > a[i + 1]) {
            int tmp = a[i + 1];
            a[i + 1] = a[i];
            a[i] = tmp;
            disSwap = true;
         }
      }
   }
}

Insertion sort, time complexity: O(N^2)

public void insertionSort(int[] a) {
   int n = a.length;
   for (int i = 1; i < n; i++) {
      int key = a[i];
      int j = i;
      while(j > 0 && a[j] > key) {
         a[j + 1] = a[j];
         j = j - 1;
         }
      a[j + 1] = key;
   }
}

Selection sort, time complexity: O(N^2)

public void selectionSort(int[] a) {
   int n = a.length;
   for (int i = 0; i < n - 1; i++) {
      int min = i;
      for (int j = i + 1; j < n; j++) {
         if(a[j] < a[min]) {
            min = j;
         }
      }
      int tmp = a[i];
      a[i] = a[min];
      a[min] = tmp;]
   }
}

Shell sort, time complexity: O(N^2)

public void shellSort(int[] arr) {
   int n = arr.length;
   for (int gap = n / 2; gap > 0; gap /= 2) {
      for (int i = gap; i < n; i++) {
      int key = arr[gap];
      int j = i;
      while (j >= gap && arr[j] > key) {
         arr[j + gap] = arr[j];
         j = j - gap;
      }
      arr[j + gap] = key;
      }
   }
}

Merge sort, time complexity: O(NlogN)

 private void merge(int[] arr, int lo, int mid, int hi) {
    int n1 = mid - lo + 1;
    int n2 = hi - mid;
    int[] L = new int[n1]; // L is arr[lo, ..., mid]
    int[] R = new int[n2]; // R is arr[mid + 1, ..., hi]
    for (int i = 0; i < n1; i++) {
       L[i] = arr[lo + i];
    }
    for (int j = 0; j < n2; j++) {
       R[j] = arr[mid + 1 + j];
    }
    int i = 0;
    int j = 0;
    int k = lo;
    while (i < n1 && j < n2) {
       if (L[i] <= R[j]) {
          arr[k] = L[i];
          i += 1;
       } else {
          arr[k] = R[j];
          j += 1;
       }
       k += 1;
    }
    while (i < n1) {
       arr[k] = L[i];
       i += 1;
       k += 1;
    }
    while (j < n2) {
       arr[k] = R[j];
       j += 1;
       k += 1;
    }
 }

private void mergeSortInner(int arr, int lo, int hi) {
  if (lo >= hi) {
    return;
  }
  int mid = lo + (hi - lo) / 2;
  mergeSortInner(arr, lo, mid);
  mergeSortInner(arr, mid + 1 , hi);
  merge(arr, lo, mid, hi);
}

public void mergeSort(int[] arr) {
  int n = arr.length;
  mergeSortHelper(arr, 0, n - 1);
}

Quick sort, time complexity: O(NlogN)

private void partition(int[] arr, int lo, int hi) {
   int x = arr[lo];
   int i = lo;
   for (int j = lo + 1; j <= hi; j++) {
      if (arr[j] <= x) {
         i += 1;
         int tmp = arr[i];
         arr[i] = arr[j];
         arr[j] = arr[i];
      }
   }
   int tmp = arr[i];
   arr[i] = arr[lo];
   arr[lo] = tmp;
   return i;
}

private void quickSortInner(int[] arr, int lo, int hi) {
   if (lo >= hi) {
      return;
   }
   int x = partition(arr, lo, hi);
   quickSortInner(arr, lo, x - 1);
   quickSortInner(arr, x + 1, hi);
}

public void quickSort(int[] arr) {
   int n = arr.length;
   quickSortInner(arr, 0, n - 1);
}

Heap

Max heap implementation with a 0-indexed array with length n

Parent, time complexity: \(O(1)\)

1
2
3

public int parent(int index) {
   return (index - 1) / 2;
}

Left child, time complexity: \(O(1)\)

public int leftChild(int index) {
   if (2 * index + 1 >= n) {
      throw new IndexOutOfBoundsException();
   }
   return 2 * index + 1;
}

Right child, time complexity: \(O(1)\)

public int rightChild(int index) {
   if (2 * index + 2 >= n) {
      throw new IndexOutOfBoundsException();
   }
   return 2 * index + 2;
}

Heapify-up, time complexity: \(O(logN)\)

public void heapifyUp(int[] arr, int index) {
   while (index > 0 && arr[parent(index)] < arr[index]) {
      int tmp = arr[parent(index)];
      arr[parent(index)] = arr[index];
      arr[index] = tmp;
      index = parent(index);
   }
}

Heapify-down, time complexity: \(O(logN)\)

public void heapifyDown(int[] arr, int n, int index) {
   int left = leftChild(index);
   int right = rightChild(index);
   int largest = index;
   if (left < n && arr[left] > arr[largest]) {
      largest = left;
   }
   if (right < n && arr[right] > arr[largest]) {
      largest = right;
   }
   if (largest != index) {
      int tmp = arr[index];
      arr[index] = arr[largest];
      arr[largest] = tmp;
      heapifyDown(arr, n, largest);
   }
}

Build-max-heap from array, time complexity: \(O(N)\)
- Consider \(n = 2^{h + 1} - 1\), which is a heap with \(n\) nodes and height \(h\) (root at level 0). At level \(h\), there are \(2^h\) nodes but no shift down is needed, at level \(h - 1\), there are \(2^{h - 1}\) nodes, and at most one shift down for each node, so the total is \(T(n) = \sum\limits_{j = 0} ^{h} j2^{h-j} \leq \sum\limits_{j = 0} ^{\infty} j2^{h-j} = n + 1 = O(n)\)
  1
  2
  3
  4
  5
  6
  public void buildMaxHeap(int[] arr) {
  n = arr.length;
  for (int i = n / 2 - 1; i >= 0; i--) {
  heapifyDown(arr, i);
  }
  }

Insert, time complexity: \(O(NlogN)\)

public void insert(int arr, int item) {
   heapSize += 1;
   int index = heapSize - 1;
   // insert item at then end, then heapify up
   arr[index] = item;
   heapifyUp(arr, index);
}

Delete max, time complexity: \(O(NlogN)\)

public int deleteMin(int arr, int item) {
   int max = arr[0];
   // swap the maximum with the last one, then heapify down
   arr[0] = arr[heapSize - 1];
   heapSize -= 1;
   heapifyDown(arr, heapSize, 0);
   return max;
}

Heap-sort, time complexity: \(O(NlogN)\)

public heapSort(int[] arr) {
   // build a max heap
   buildMaxHeap(arr);
   for (int i = n - 1; i > 0; i--) {
      // swap the largest to the last one, reduce heap size, then heapify down
      int tmp = arr[0];
      arr[0] = arr[i];
      arr[i] = tmp;
      heapifyDown(arr, i - 1, 0);
   }
}

Graph

BFS, time complexity: \(O(V + E)\)

public void bfs(Graph G, int s) {
   boolean[] visited = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
   }
   Queue<Integer> queue = new LinkedList<Integer>();
   queue.add(s);
   visited[s] = true;
   while (!queue.isEmpty()) {
      int v = queue.poll();
      // do something with v
      for (int w: G.adj(v)) {
         if (!visited[w]) {
            queue.add(w);
            visited[w] = true;
         }
      }
   }
}

Dijkstra, time complexity: \(O((V + E)logV)\) with PriorityQueue, \(O(V^2)\) with array

 public int[] dijkstra(G, int src) {
   int[] dist = new int[G.V()];
   // prev[i] is the previous vertex of vertex i in the shortest path from src to i
   // path from src to i is prev[i] -> prev[prev[i]] -> ... -> src
   int[] prev = new int[G.V()];
   for (int i = 0; i < G.V(); i++) {
     dist[i] = Integer.MAX_VALUE;
     prev[i] = -1;
   }
   dist[src] = 0;
   prev[i] = -1;
   PriorityQueue<Integer> pq = new PriorityQueue<Integer>(G.V(), new Comparator<Integer>() {
     public int compare(Integer a, Integer b) {
       return dist[a] - dist[b];
     }
   });
   for (int i = 0; i < G.V(); i++) {
     pq.enqueue(i, dist[i]);
   }
   while (pq.isEmpty()) {
     int u = pq.remove();
     for(int v: G.adj(u)) {
       if (dist[v] > dist[u] + G.weight(u, v)) {
         dist[v] = dist[u] + G.weight(u, v);
         prev[v] = u;
       }
     }
   }
   return dist;
}

DFS, time complexity: \(O(V + E)\)

// iterative
public void dfs(Graph G, int s) {
   boolean[] visited = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
   }
   Stack<Integer> stack = new Stack<Integer>();
   stack.push(s);
   visited[s] = true;
   while (!stack.isEmpty()) {
      int v = stack.pop();
      // do something with v
      for (int w: G.adj(v)) {
         if (!visited[w]) {
            stack.push(w);
            visited[w] = true;
         }
      }
   }  
}

// recursive
public void dfs(Graph G, int s) {
   boolean[] visited = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
   }
   dfs(G, s, visited);
}
private void dfs(Graph G, int v, boolean[] visited) {
   visited[v] = true;
   for (int w: G.adj(v)) {
      if (!visited[w]) {
         dfs(G, w, visited);
      }
   }
}

Find cycle in undirected graph, time complexity: \(O(V + E)\)

Idea: if we can reach w from v in different ways, then there must be a cycle

public boolean hasCycle(Graph G) {
   boolean[] visited = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
   }
   for (int s = 0; i < G.V(); s++) {
      if (!visited[s]) {
         if (hasCycle(G, s, s, visited)) {
            return true;
         }
      }
   }
   return false;
}

private boolean hasCycle(Graph G, int v, int u, boolean[] visited) {
   visited[v] = true;
   for (int w: G.adj(v)) {
      if (!visited[w]) {
         hasCycle(G, w, v, visited);
      } else if (w != u) {
         return true;
      }
   }
   return false;
}

Find cycle in directed graph, time complexity: \(O(V + E)\)

public boolean hasCycle(Graph G) {
   boolean[] visited = new boolean[G.V()];
   boolean[] onStack = new boolean[G.V()];
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
      onStack[i] = false;
   }
   for (int i = 0; i < G.B(); i++) {
      if (!visited[i]) {
         if (hasCycle(G, i, i, visited, onStack)) {
            return true;
         }
      }
   }
   return false;
}

private boolean hasCycle(Graph G, int v, int u, boolean[] visited, boolean[] onStack) {
   visited[v] = true;
   onStack[v] = true;
   for (int w: G.adj(v)) {
      if (!visited[w]) {
         if (hasCycle(G, w, v, visited, onStack)) {
            return true;
         }
      } else if (onStack[w]) {
         return true;
      }
   }
   onStack[v] = false;
   return false;
}

Find SCC in directed graphs, time complexity: \(O(V + E)\)

public int scc(Graph G) {
   boolean[] visited = new boolean[G.V()];
   int[] id = new int[G.V()];
   int count = 0;
   for (int i = 0; i < G.V(); i++) {
      visited[i] = false;
      id[i] = -1;
   }
   for (int i = 0; i < G.V(); i++) {
      if (!visited[i]) {
         dfs(G, i, visited, id, count);
         count += 1;
      }
   }
   return count;
}

private void dfs(Graph G, int v, boolean[] visited, int[] id, int count) {
   visited[v] = true;
   id[v] = count;
   for (int w: G.adj(v)) {
      if (!visited[w]) {
         dfs(G, w, visited, id, count);
      }
   }
}