Possible Bipartition
Real-world version: Kennel Split Into Two YardsThe statement here is our own: the same inputs, outputs and technique.
A shelter is boarding dogs dogs, tagged 1 through dogs, and has exactly two fenced yards. Every dog must be put in one of the two yards.
The handlers keep a feud list. feuds[i] = [a, b] means dog a and dog b fight and must not share a yard. Each entry has a < b, and no pair of dogs is listed twice.
Return true if there is a way to place every dog so that no feuding pair shares a yard, and false otherwise. The two yards do not have to hold the same number of dogs, and one of them may be left empty.
Examples
Example 1
- Input
- dogs = 4, feuds = [[1, 2], [1, 3], [2, 4], [3, 4]]
- Output
- true
Put dogs 1 and 4 in one yard and dogs 2 and 3 in the other. Checking the list: 1 is apart from 2 and 3, and 4 is apart from 2 and 3.
Example 2
- Input
- dogs = 5, feuds = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 1]]
- Output
- false
The five feuds form a ring 1-2-3-4-5-1. Walking the ring forces the yards to alternate, and after five steps dog 1 would have to be in the other yard from itself.
Example 3
- Input
- dogs = 6, feuds = [[1, 4], [2, 5], [3, 6]]
- Output
- true
Dogs 1, 2 and 3 go in one yard and dogs 4, 5 and 6 in the other, which separates all three feuding pairs.
Example 4
- Input
- dogs = 6, feuds = [[1, 2], [3, 4], [4, 5], [5, 3]]
- Output
- false
Dogs 3, 4 and 5 all feud with each other, and two of those three would have to share a yard. Dog 6 has no feuds at all, and dogs 1 and 2 could be separated easily, but the answer is still false.
Example 5
- Input
- dogs = 3, feuds = []
- Output
- true
With no feuds recorded, every dog can go in the first yard.
Constraints
- 1 <= dogs <= 2000
- 0 <= feuds.length <= 10^4
- feuds[i].length == 2
- 1 <= a < b <= dogs
- All pairs in feuds are different.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def can_split_kennel(dogs: int, feuds: list[list[int]]) -> bool:public boolean canSplitKennel(int dogs, int[][] feuds)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 5 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's