1042.不邻接植花.md

1042.不邻接植花

/*
 * @lc app=leetcode.cn id=1042 lang=typescript
 *
 * [1042] 不邻接植花
 */

// @lc code=start
function gardenNoAdj(n: number, paths: number[][]): number[] {}
// @lc code=end

解法 1: 染色法

function gardenNoAdj(n: number, paths: number[][]): number[] {
  const h = new Array(n).fill(-1),
    ne: number[] = [],
    e: number[] = []
  const add = (i: number, j: number) => (e.push(j), ne.push(h[i]), (h[i] = ne.length - 1))
  for (let [u, v] of paths) {
    add(u - 1, v - 1)
    add(v - 1, u - 1)
  }
  const state: number[] = new Array(n).fill(0),
    res: number[] = []

  for (let u = 0; u < n; u++) {
    for (let i = 0; i < 4; i++) {
      if (state[u] & (1 << i)) continue
      res[u] = i
      break
    }
    for (let i = h[u]; ~i; i = ne[i]) {
      const v = e[i]
      if (res[v] !== undefined) continue
      state[v] |= 1 << res[u]
    }
  }
  return res.map(a => a + 1)
}

Case

test.each([
  {
    input: {
      n: 3,
      paths: [
        [1, 2],
        [2, 3],
        [3, 1],
      ],
    },
    output: [1, 2, 3],
  },
  {
    input: {
      n: 4,
      paths: [
        [1, 2],
        [3, 4],
      ],
    },
    output: [1, 2, 1, 2],
  },
  {
    input: {
      n: 4,
      paths: [
        [1, 2],
        [2, 3],
        [3, 4],
        [4, 1],
        [1, 3],
        [2, 4],
      ],
    },
    output: [1, 2, 3, 4],
  },
])('input: n = $input.n, paths = $input.paths', ({ input: { n, paths }, output }) => {
  expect(gardenNoAdj(n, paths)).toEqual(output)
})