Press "Enter" to skip to content

Posts published in “Graph”

花花酱 LeetCode 1042. Flower Planting With No Adjacent

You have N gardens, labelled 1 to N.  In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden.  The flower types are denoted 1, 2, 3, or 4.  It is guaranteed an answer exists.

Example 1:

Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

Example 2:

Input: N = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Note:

  • 1 <= N <= 10000
  • 0 <= paths.size <= 20000
  • No garden has 4 or more paths coming into or leaving it.
  • It is guaranteed an answer exists.

Solution: Graph coloring, choose any available color

Time complexity: O(|V|+|E|)
Space complexity: O(|V|+|E|)

C++

花花酱 LeetCode 851. Loud and Rich

In a group of N people (labelled 0, 1, 2, ..., N-1), each person has different amounts of money, and different levels of quietness.

For convenience, we’ll call the person with label x, simply “person x“.

We’ll say that richer[i] = [x, y] if person x definitely has more money than person y.  Note that richer may only be a subset of valid observations.

Also, we’ll say quiet[x] = q if person x has quietness q.

Now, return answer, where answer[x] = y if y is the least quiet person (that is, the person y with the smallest value of quiet[y]), among all people who definitely have equal to or more money than person x.

Example 1:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but
it isn't clear if they have more money than person 0.

answer[7] = 7.
Among all people that definitely have equal to or more money than person 7
(which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x])
is person 7.

The other answers can be filled out with similar reasoning.

Note:

  1. 1 <= quiet.length = N <= 500
  2. 0 <= quiet[i] < N, all quiet[i] are different.
  3. 0 <= richer.length <= N * (N-1) / 2
  4. 0 <= richer[i][j] < N
  5. richer[i][0] != richer[i][1]
  6. richer[i]‘s are all different.
  7. The observations in richer are all logically consistent.

Solution: DFS + Memoization

For person i , remember the quietest person who is richer than person i.

Time complexity: O(n^2)
Space complexity: O(n)

C++

花花酱 LeetCode 997. Find the Town Judge

In a town, there are N people labelled from 1 to N.  There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

  1. The town judge trusts nobody.
  2. Everybody (except for the town judge) trusts the town judge.
  3. There is exactly one person that satisfies properties 1 and 2.

You are given trust, an array of pairs trust[i] = [a, b] representing that the person labelled a trusts the person labelled b.

If the town judge exists and can be identified, return the label of the town judge.  Otherwise, return -1.

Example 1:

Input: N = 2, trust = [[1,2]]
Output: 2

Example 2:

Input: N = 3, trust = [[1,3],[2,3]]
Output: 3

Example 3:

Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1

Example 4:

Input: N = 3, trust = [[1,2],[2,3]]
Output: -1

Example 5:

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3

Note:

  1. 1 <= N <= 1000
  2. trust.length <= 10000
  3. trust[i] are all different
  4. trust[i][0] != trust[i][1]
  5. 1 <= trust[i][0], trust[i][1] <= N

Solution: Degree

node with degree (in_degree – out_degree) N – 1 is the judge.

Time complexity: O(N+T)
Space complexity: O(N)

C++

花花酱 LeetCode 996. Number of Squareful Arrays

Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful.  Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Input: [1,17,8]
Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

  1. 1 <= A.length <= 12
  2. 0 <= A[i] <= 1e9

Solution1: DFS

Try all permutations with pruning.

Time complexity: O(n!)
Space complexity: O(n)

C++

Solution 2: DP Hamiltonian Path

dp[s][i] := # of ways to reach state s (binary mask of nodes visited) that ends with node i

dp[s | (1 << j)][j] += dp[s][i] if g[i][j]

Time complexity: O(n^2*2^n)
Space complexity: O(2^n)

C++

Related Problems

花花酱 LeetCode 133. Clone Graph

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.
OJ’s undirected graph serialization (so you can understand error output):

Nodes are labeled uniquely.We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.

Solution: Queue + Hashtable

Time complexity: O(V+E)
Space complexity: O(V+E)

C++