Cycle Detection in Directed Graph in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the visited array to zero.

DSA C

int visited[V] = {0};
for (int i = 0; i < V; i++) {
    visited[i] = [1];
}

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

A1

B0

C-1

DV

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing visited array with 1 instead of 0.

Using uninitialized values causing unpredictable behavior.

The visited array should be initialized to 0 to mark all nodes as unvisited at the start.

2fill in blank

medium

Complete the code to mark the current node as visited in DFS.

DSA C

void dfs(int node) {
    visited[node] = [1];
    // rest of DFS code
}

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

A1

B2

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited[node] as 0 or 2 incorrectly.

Not marking the node at all.

Marking the node as 1 means it is currently being visited in the DFS path.

3fill in blank

hard

Fix the error in the condition to detect a cycle in DFS.

DSA C

for (int i = 0; i < adj[node].size(); i++) {
    int next = adj[node][i];
    if (visited[next] == [1]) {
        return 1; // cycle detected
    }
}

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

A1

B2

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for visited[next] == 0 instead of 1.

Using wrong values like 2 or -1.

If visited[next] == 1, it means the node is in the current recursion stack, indicating a cycle.

4fill in blank

hard

Fill both blanks to correctly mark nodes after DFS call.

DSA C

visited[node] = [1];
for (int i = 0; i < adj[node].size(); i++) {
    int next = adj[node][i];
    if (visited[next] == 0 && dfs(next)) {
        return 1;
    }
}
visited[node] = [2];
return 0;

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

A1

B0

C2

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Not marking node as 2 after DFS.

Marking node as 0 instead of 1 initially.

Mark node as 1 when visiting, and 2 after all descendants are processed to indicate done.

5fill in blank

hard

Fill all three blanks to complete the cycle detection function.

DSA C

int isCyclic() {
    for (int i = 0; i < V; i++) {
        if (visited[i] == [1]) {
            if (dfs(i) == [2]) {
                return [3];
            }
        }
    }
    return 0;
}

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

A0

B1

C2

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting DFS from visited nodes.

Returning wrong values on cycle detection.

Start DFS from unvisited nodes (visited[i] == 0). If dfs returns 1 (cycle found), return 1.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. Whether there is a path that starts and ends at the same node following edge directions

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. The maximum degree of any node

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same node following the direction of edges.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following edge directions -> Option A

4. Quick Check:

   Cycle detection = path starting and ending at same node [OK]

Hint: Cycle means path loops back to start following edges [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Thinking cycle ignores edge directions
• Mixing cycle detection with counting nodes

2. Which of the following is the correct way to declare a visited array for cycle detection in C for a graph with n nodes?

easy

A. int visited = new int[n];

B. int visited[n] = {0};

C. int visited[] = {0};

D. int visited[n];

Solution

1. Step 1: Understand array declaration in C

   In C, to declare an array of size n, use int visited[n]; but it is uninitialized.

2. Step 2: Initialize array to zero

   To initialize all elements to zero, use int visited[n] = {0}; which sets all to zero.

3. Final Answer:

   int visited[n] = {0}; -> Option B

4. Quick Check:

   Array declaration with zero init = int visited[n] = {0}; [OK]

Hint: Use int arr[n] = {0} to initialize all zeros in C [OK]

Common Mistakes:

• Using 'new' keyword which is C++ not C
• Declaring array without size
• Incorrect initialization syntax

3. Consider the following C code snippet for cycle detection in a directed graph using DFS. What will be the output?

void dfs(int node, int visited[], int recStack[], int graph[][3]) {
    visited[node] = 1;
    recStack[node] = 1;
    for (int i = 0; i < 3; i++) {
        int adj = graph[node][i];
        if (adj == -1) continue;
        if (!visited[adj]) dfs(adj, visited, recStack, graph);
        else if (recStack[adj]) printf("Cycle detected\n");
    }
    recStack[node] = 0;
}

int main() {
    int graph[3][3] = {{1, -1, -1}, {2, -1, -1}, {0, -1, -1}};
    int visited[3] = {0}, recStack[3] = {0};
    dfs(0, visited, recStack, graph);
    return 0;
}

medium

A. No output

B. Infinite loop

C. Segmentation fault

D. Cycle detected

Solution

1. Step 1: Analyze graph edges

   Graph edges: 0->1, 1->2, 2->0 form a cycle.

2. Step 2: Trace DFS calls and cycle detection

   DFS visits 0, then 1, then 2. When 2 tries to visit 0 again which is in recursion stack, it prints "Cycle detected".

3. Final Answer:

   Cycle detected -> Option D

4. Quick Check:

   Cycle in graph triggers print "Cycle detected" [OK]

Hint: Cycle prints when node revisited in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Assuming no output means no cycle
• Confusing visited and recursion stack arrays

4. The following code attempts to detect a cycle in a directed graph but does not work correctly. What is the main error?

void dfs(int node, int visited[], int graph[][3]) {
    visited[node] = 1;
    for (int i = 0; i < 3; i++) {
        int adj = graph[node][i];
        if (adj == -1) continue;
        if (!visited[adj]) dfs(adj, visited, graph);
        else printf("Cycle detected\n");
    }
}

int main() {
    int graph[3][3] = {{1, -1, -1}, {2, -1, -1}, {0, -1, -1}};
    int visited[3] = {0};
    dfs(0, visited, graph);
    return 0;
}

medium

A. Graph adjacency matrix is incorrect

B. Visited array is not initialized

C. Missing recursion stack to track nodes in current path

D. DFS function missing return type

Solution

1. Step 1: Understand cycle detection logic

   Cycle detection in directed graph needs to track nodes in current recursion path using a recursion stack.

2. Step 2: Identify missing recursion stack

   This code only uses visited array, so it cannot distinguish back edges causing cycles from cross edges.

3. Final Answer:

   Missing recursion stack to track nodes in current path -> Option C

4. Quick Check:

   Recursion stack needed for correct cycle detection [OK]

Hint: Use recursion stack to detect back edges in DFS [OK]

Common Mistakes:

• Assuming visited array alone detects cycles
• Ignoring need to track current DFS path
• Confusing undirected and directed cycle detection

5. You have a directed graph represented as adjacency lists:

0: [1]
1: [2]
2: [3, 4]
3: [1]
4: []

Which nodes are part of a cycle detected by DFS cycle detection algorithm?

hard

A. Nodes 1, 2, 3

B. Nodes 0, 1, 4

C. Nodes 0, 2, 4

D. Nodes 3, 4

Solution

1. Step 1: Trace the graph edges

   Edges: 0->1, 1->2, 2->3 and 2->4, 3->1.

2. Step 2: Identify cycle nodes

   Cycle is 1->2->3->1. Nodes 1, 2, 3 form the cycle.

3. Final Answer:

   Nodes 1, 2, 3 -> Option A

4. Quick Check:

   Cycle nodes = 1, 2, 3 [OK]

Hint: Follow edges to find loops including nodes [OK]

Common Mistakes:

• Including nodes not in cycle like 0 or 4
• Missing node 3 in cycle
• Confusing cycle with path