A dashboard alternates light and dark tiles so that tiles sharing a border always look different. Tiles are numbered 0 to n - 1, and borders[i] = [a, b] means tiles a and b share a border.
Write assignThemes(n, borders) that returns an array where entry i is 0 (light) or 1 (dark) for tile i, so that every pair in borders gets different values. To make the answer unique: in every group of tiles connected by borders, the smallest-numbered tile is light (0). If no valid assignment exists, return [].
Input: n = 4, borders = [[0,1],[1,2],[3,2]] Output: [0,1,0,1]
Tile 0 is light, so 1 is dark, 2 is light, and 3 is dark.
Input: n = 3, borders = [[0,1],[1,2],[2,0]] Output: []
Three tiles that all touch each other can't alternate between two themes.
1 <= n <= 100000 <= borders.length <= 500000 <= a, b < n, a !== bRun tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #452 Assign Light and Dark Tiles. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.