0
0
DSA Cprogramming~10 mins

Cycle Detection in Undirected Graph in DSA C - Interactive Practice

Choose your learning style9 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Practice - 5 Tasks
Answer the questions below
1fill in blank
easy

Complete the code to initialize the adjacency list for the graph.

DSA C
int adj[V];
for (int i = 0; i < V; i++) {
    adj[i] = [1];
}
Drag options to blanks, or click blank then click option'
ANULL
B-1
C0
D1
Attempts:
3 left
💡 Hint
Common Mistakes
Initializing adjacency list elements to 0 or 1 instead of NULL.
Not initializing adjacency list before use.
2fill in blank
medium

Complete the code to add an edge between two vertices u and v in the adjacency list.

DSA C
void addEdge(struct Node* adj[], int u, int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = adj[u];
    adj[u] = [1];
}
Drag options to blanks, or click blank then click option'
AnewNode
Bv
Cadj[u]
DnewNode->next
Attempts:
3 left
💡 Hint
Common Mistakes
Assigning adj[u] to newNode->next instead of the other way.
Assigning wrong pointer to adj[u].
3fill in blank
hard

Fix the error in the DFS function to detect a cycle in the undirected graph.

DSA C
bool dfs(int v, bool visited[], int parent, struct Node* adj[]) {
    visited[v] = true;
    struct Node* temp = adj[v];
    while (temp != NULL) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            if (dfs(adjVertex, visited, v, adj) == [1]) {
                return true;
            }
        } else if (adjVertex != parent) {
            return true;
        }
        temp = temp->next;
    }
    return false;
}
Drag options to blanks, or click blank then click option'
Afalse
Btrue
Cvisited[adjVertex]
Dparent
Attempts:
3 left
💡 Hint
Common Mistakes
Returning false instead of true when cycle detected in recursion.
Confusing parent vertex check.
4fill in blank
hard

Fill both blanks to complete the cycle detection function that iterates over all vertices.

DSA C
bool isCycle(struct Node* adj[], int V) {
    bool visited[V];
    for (int i = 0; i < V; i++)
        visited[i] = [1];
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, visited, [2], adj)) {
                return true;
            }
        }
    }
    return false;
}
Drag options to blanks, or click blank then click option'
Afalse
Btrue
C-1
D0
Attempts:
3 left
💡 Hint
Common Mistakes
Initializing visited[] to true instead of false.
Using 0 as parent for root vertex causing false cycle detection.
5fill in blank
hard

Fill all three blanks to complete the main function that builds the graph and checks for cycles.

DSA C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node {
    int vertex;
    struct Node* next;
};

int main() {
    int V = 5;
    struct Node* adj[V];
    for (int i = 0; i < V; i++)
        adj[i] = NULL;

    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);
    addEdge(adj, 4, [1]);

    if (isCycle(adj, V))
        printf("Cycle detected\n");
    else
        printf("No cycle detected\n");

    return [2];
}

void addEdge(struct Node* adj[], int u, int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = adj[u];
    adj[u] = newNode;

    newNode = malloc(sizeof(struct Node));
    newNode->vertex = u;
    newNode->next = adj[v];
    adj[v] = newNode;
}

bool isCycle(struct Node* adj[], int V);
bool dfs(int v, bool visited[], int parent, struct Node* adj[]);
Drag options to blanks, or click blank then click option'
A0
B1
C5
Attempts:
3 left
💡 Hint
Common Mistakes
Connecting vertex 4 to 0 instead of 1, changing the cycle structure.
Returning non-zero value from main.