Practice - 5 Tasks

Answer the questions below

1fill in blank

easy

Complete the code to initialize the colors vector with -1 for all nodes.

DSA Rust

let mut colors = vec![[1]; graph.len()];

Drag options to blanks, or click blank then click option'

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 which represents a colored node.

Using 1 which represents the opposite color.

Using 2 which is unnecessary for bipartite graphs.

✗ Incorrect

The correct value to initialize uncolored nodes is -1. vec![-1; graph.len()] creates a vector of length graph.len() filled with -1.

2fill in blank

medium

Complete the code to assign the starting node color as 0.

DSA Rust

colors[start] = [1];

Drag options to blanks, or click blank then click option'

B-1

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning -1 which means uncolored.

Assigning 1 which is the other color but not the start.

✗ Incorrect

We assign color 0 to the starting node to begin the bipartite coloring process.

3fill in blank

hard

Fix the error in the BFS loop condition to process nodes until the queue is empty.

DSA Rust

while let Some(node) = queue.[1]() {

Drag options to blanks, or click blank then click option'

Apop_front

Bpop

Cremove

Dpop_back

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop() which is not defined for VecDeque.

Using pop_back() which leads to DFS behavior.

✗ Incorrect

Using pop_front() removes and returns the first element from the queue, which is correct for BFS.

4fill in blank

hard

Fill both blanks to assign the opposite color to the neighbor and push it to the queue.

DSA Rust

colors[neighbor] = 1 [1] colors[node];
queue.[2](neighbor);

Drag options to blanks, or click blank then click option'

B+

C-

Dpush_back

Attempts:

3 left

💡 Hint

Common Mistakes

Using + or - instead of XOR for color flipping.

Using push instead of push_back for VecDeque.

✗ Incorrect

XOR with 1 flips the color between 0 and 1. push_back adds the neighbor to the end of the queue.

5fill in blank

hard

Fill all three blanks to check if a neighbor has the same color as the current node and return false if so.

DSA Rust

if colors[neighbor] != -1 && colors[neighbor] [1] colors[node] {
    return [2];
}

// After BFS loop
return [3];

Drag options to blanks, or click blank then click option'

A==

Bfalse

Ctrue

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using != instead of == to check color conflict.

Returning true inside the loop instead of after.

✗ Incorrect

If neighbor color equals current node color, graph is not bipartite, so return false. After BFS, return true.

Practice

(1/5)

1. What does it mean for a graph to be bipartite?

easy

A. Its vertices can be divided into two groups with no edges inside the same group

B. It has an equal number of vertices and edges

C. It contains at least one cycle of odd length

D. All vertices have the same degree

Solution

Step 1: Understand bipartite graph definition
A bipartite graph is one where vertices can be split into two sets so that no edge connects vertices within the same set.
Step 2: Check options against definition
Its vertices can be divided into two groups with no edges inside the same group matches this definition exactly. Options A, B, and D describe unrelated properties.
Final Answer:
Its vertices can be divided into two groups with no edges inside the same group -> Option A
Quick Check:
Bipartite graph = two groups, no internal edges [OK]

Hint: Bipartite means two groups with no edges inside groups [OK]

Common Mistakes:

Confusing bipartite with equal vertices and edges
Thinking bipartite graphs must have cycles
Assuming all vertices have same degree

2. Which Rust code snippet correctly declares an adjacency list for an undirected graph to check bipartiteness?

easy

A. let graph: Vec<(usize, usize)> = Vec::new();

B. let graph: Vec<usize> = vec![0; n];

C. let graph: HashMap = HashMap::new();

D. let graph: Vec = vec![vec![]; n];

Solution

Step 1: Identify adjacency list type
An adjacency list for a graph is usually a vector of vectors, where each inner vector holds neighbors of a vertex.
Step 2: Match code snippet to adjacency list
let graph: Vec = vec![vec![]; n]; declares a vector of vectors of usize, initialized with empty vectors for each vertex, which is correct. Options A, B, and C do not represent adjacency lists properly.
Final Answer:
let graph: Vec = vec![vec![]; n]; -> Option D
Quick Check:
Adjacency list = Vec of Vecs [OK]

Hint: Adjacency list is Vec in Rust [OK]

Common Mistakes:

Using Vec<usize> instead of Vec
Using HashMap with wrong types
Using tuple vector which is edge list, not adjacency list

3. Given the following Rust code snippet to check bipartiteness, what is the output?

let graph = vec![
    vec![1, 3],
    vec![0, 2],
    vec![1, 3],
    vec![0, 2],
];

fn is_bipartite(graph: &Vec) -> bool {
    let n = graph.len();
    let mut colors = vec![-1; n];
    for i in 0..n {
        if colors[i] == -1 {
            let mut stack = vec![i];
            colors[i] = 0;
            while let Some(u) = stack.pop() {
                for &v in &graph[u] {
                    if colors[v] == -1 {
                        colors[v] = 1 - colors[u];
                        stack.push(v);
                    } else if colors[v] == colors[u] {
                        return false;
                    }
                }
            }
        }
    }
    true
}

println!("{}", is_bipartite(&graph));

medium

A. true

B. false

C. Compilation error

D. Runtime panic

Solution

Step 1: Analyze graph structure
The graph has 4 vertices with edges forming a square (0-1-2-3-0). This is an even cycle, which is bipartite.
Step 2: Trace DFS coloring
The code colors vertex 0 as 0, then neighbors 1 and 3 as 1, then neighbors 2 as 0. No conflicts occur, so it returns true.
Final Answer:
true -> Option A
Quick Check:
Even cycle graph is bipartite = true [OK]

Hint: Even cycles are bipartite, so output is true [OK]

Common Mistakes:

Thinking all cycles are non-bipartite
Confusing stack usage with queue
Missing color conflict check

4. The following Rust code attempts to check if a graph is bipartite but has a bug. What is the bug?

fn is_bipartite(graph: &Vec) -> bool {
    let n = graph.len();
    let mut colors = vec![-1; n];
    for i in 0..n {
        if colors[i] == -1 {
            let mut stack = vec![i];
            colors[i] = 0;
            while let Some(u) = stack.pop() {
                for &v in &graph[u] {
                    if colors[v] == -1 {
                        colors[v] = colors[u]; // Bug here
                        stack.push(v);
                    } else if colors[v] == colors[u] {
                        return false;
                    }
                }
            }
        }
    }
    true
}

medium

A. Stack is used instead of queue, causing infinite loop

B. Colors assigned to neighbors are same as current vertex, causing wrong bipartite check

C. colors vector is initialized with zeros instead of -1

D. Graph parameter should be mutable

Solution

Step 1: Identify color assignment bug
The code assigns neighbors the same color as current vertex, which breaks bipartite property requiring opposite colors.
Step 2: Understand impact on bipartite check
This causes false negatives or positives because neighbors must have opposite colors, so the check fails.
Final Answer:
Colors assigned to neighbors are same as current vertex, causing wrong bipartite check -> Option B
Quick Check:
Neighbors must have opposite colors [OK]

Hint: Neighbors must get opposite color, not same [OK]

Common Mistakes:

Assigning same color to neighbors
Confusing stack and queue usage
Initializing colors incorrectly

5. You have a graph with vertices 0 to 5 and edges: (0-1), (1-2), (2-3), (3-0), (3-4), (4-5). Which of the following statements is true about its bipartiteness?

hard

A. The graph is not bipartite because it contains an odd cycle (3-4-5)

B. The graph is not bipartite because it contains an even cycle (0-1-2-3)

C. The graph is bipartite because it contains no odd cycles

D. The graph is bipartite because all vertices have degree 2 or less

Solution

Step 1: Identify cycles in the graph
The graph has a cycle 0-1-2-3-0 which is length 4 (even). The path 3-4-5 is a chain, not a cycle.
Step 2: Check bipartite condition
Graphs with no odd cycles are bipartite. Since the only cycle is even, the graph is bipartite.
Final Answer:
The graph is bipartite because it contains no odd cycles -> Option C
Quick Check:
No odd cycles means bipartite [OK]

Hint: Check for odd cycles; none means bipartite [OK]

Common Mistakes:

Mistaking chains for cycles
Thinking even cycles break bipartiteness
Assuming degree affects bipartiteness

Bipartite Graph Check in DSA Rust - Interactive Practice

Practice

Solution

Step 1: Understand bipartite graph definition

Step 2: Check options against definition

Final Answer:

Quick Check:

Solution

Step 1: Identify adjacency list type

Step 2: Match code snippet to adjacency list

Final Answer:

Quick Check:

Solution

Step 1: Analyze graph structure

Step 2: Trace DFS coloring

Final Answer:

Quick Check:

Solution

Step 1: Identify color assignment bug

Step 2: Understand impact on bipartite check

Final Answer:

Quick Check:

Solution

Step 1: Identify cycles in the graph

Step 2: Check bipartite condition

Final Answer:

Quick Check:

Ready to prove it?