Is Graph Bipartite?
Two study groups, no feuds. You are splitting n students into two groups. graph[u] lists the students that student u feuds with. Feuds go both ways (if v is in graph[u], then u is in graph[v]), nobody feuds with themself, and no feud is listed twice. Some students may have no feud at all, and the feuds may leave the students in several separate clusters. Return True if everyone can be put in one of the two groups so that no two students in the same group feud, and False otherwise. Limits: 1 <= n <= 200000 students, and at most 400000 numbers in all the lists together. Heads-up: a long chain of feuds makes a recursive walk go very deep, and Python stops at 1000 calls by default, so a loop with your own queue or stack is the safer choice. Examples: graph = [[3,4],[3,4],[5],[0,1],[0,1],[2]] => True group A = {0, 1, 2}, group B = {3, 4, 5} graph = [[1,2],[0,2],[0,1]] => False three students who all feud with each other cannot fit into two groups
You're splitting students into two study groups so nobody shares a group with someone they feud with, and you need to say whether that's even possible. Interviewers like it because a seating puzzle turns out to be a graph walk, and the walk has to cope with feuds that leave the students in several separate clusters. The classic trap is checking only the first cluster and missing the odd loop hiding in a later one. Expect up to 200,000 students and 400,000 numbers across all the lists.
Examples
You write
is_bipartite(graph: List[List[int]])
Example 1
- Input
- graph = [[3,4],[3,4],[5],[0,1],[0,1],[2]]
- returns
- true
Example 2
- Input
- graph = [[1,2],[0,2],[0,1]]
- returns
- false
Save this for your laptop
The editor and Run need a bigger screen. The link opens Is Graph Bipartite? ready to code. It is free, and the editor needs no account.
The pattern behind it
Graphs
I reach for it when
- The input is edges, prerequisites or connections.
- You need cycles, an ordering or connected groups.
Say this before you type. Say whether the edges are directed, and which of the three jobs you are doing.
All 32 Graphs problemsBFS & DFS
I reach for it when
- You walk a grid, a graph or a tree and visit each cell once.
- The word shortest appears and every step costs the same.
Say this before you type. Say why breadth or depth fits, and exactly when a cell counts as visited.
All 52 BFS & DFS problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.