graph

• Union find:
  if two connected node fail to union, there is a cycle
• Search and HashMap:
  if the non-parent neighbor of a node has been visited, there is a cycle

• each node only has <= 3 neighbors AND there is no cycle in the graph

Leetcode 261. Graph Valid Tree

1 2 3 4 5 6 7 8

public boolean validTree(int n, int[][] edges) { if (edges.length != n - 1) return false; UF set = new UF(n); for (int[] edge : edges) { if (!set.union(edge[0], edge[1])) return false; } return true; }

Leetcode 684. Redundant Connection
Leetcode 685. Redundant Connection II