0312MediumDepth-First SearchBreadth-First SearchUnion-FindGraph TheoryGraph ColoringBipartite Graph

Kennel Split Into Two Yards

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_split_kennel(dogs: int, feuds: list[list[int]]) -> bool:

Java

public boolean canSplitKennel(int dogs, int[][] feuds)

The intended approach

Time O(n + m)Space O(n + m)

Build a two-way adjacency list from the feuds, then label yards by walking the feud graph. Start each unlabelled dog in yard 1 and push it onto an explicit stack; every dog pulled off the stack hands the opposite label to its unlabelled rivals, and any rival already carrying the same label is a contradiction. The walk restarts at every dog so separate groups of dogs are all covered.

Pythonentry point: can_split_kennel

def can_split_kennel(dogs, feuds):
    # O(n + m) time: every dog is expanded once and every feud is read twice.
    # O(n + m) space for the adjacency lists, the yard labels and the stack.
    adj = [[] for _ in range(dogs + 1)]
    for pair in feuds:
        a = pair[0]
        b = pair[1]
        adj[a].append(b)
        adj[b].append(a)
    yard = [0] * (dogs + 1)
    for start in range(1, dogs + 1):
        if yard[start] != 0:
            continue
        yard[start] = 1
        stack = [start]
        while stack:
            cur = stack.pop()
            for nxt in adj[cur]:
                if yard[nxt] == 0:
                    yard[nxt] = -yard[cur]
                    stack.append(nxt)
                elif yard[nxt] == yard[cur]:
                    return False
    return True

The obvious version

Give every dog two slots, one per yard, and merge slots with a disjoint-set structure: each feud merges dog a with b's opposite slot and dog b with a's opposite slot, failing if a and b ever land in the same group.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_split_kennel(dogs, feuds):
    parent = list(range(2 * dogs + 2))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def join(x, y):
        rx = find(x)
        ry = find(y)
        if rx != ry:
            parent[rx] = ry

    for pair in feuds:
        a = pair[0]
        b = pair[1]
        if find(a) == find(b):
            return False
        join(a, b + dogs)
        join(b, a + dogs)
    return True

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in