Adjacency List Representation in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list after adding edges

What is the printed adjacency list after running the following C++ code?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int V = 3;
    vector<int> adj[V];
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(0);

    for (int i = 0; i < V; i++) {
        cout << i << ": ";
        for (auto v : adj[i]) {
            cout << v << " -> ";
        }
        cout << "null" << endl;
    }
    return 0;
}

A

0: 1 -> 2 -> null
1: 2 -> null
2: 0 -> null

B

0: 1 -> null
1: 0 -> 2 -> null
2: 0 -> null

C

0: 1 -> null
1: 2 -> null
2: 0 -> null

D

0: null
1: 2 -> null
2: 0 -> null

💡 Hint

Check which vertices are connected to each vertex by the push_back calls.

The code adds edges 0->1, 1->2, and 2->0. So adjacency list for 0 has 1, for 1 has 2, and for 2 has 0.

🧠 Conceptual

intermediate

Number of edges in adjacency list

If an undirected graph with 4 vertices has the following adjacency list representation: 0: 1 -> 2 -> null 1: 0 -> 3 -> null 2: 0 -> null 3: 1 -> null How many edges does the graph have?

A 5

B 4

C 6

D 3

💡 Hint

Each edge appears twice in an undirected graph adjacency list.

Counting all neighbors: 0 has 2, 1 has 2, 2 has 1, 3 has 1. Total 6 entries. Each edge counted twice, so edges = 6/2 = 3.

🔧 Debug

advanced

Identify the bug in adjacency list initialization

What error will this C++ code produce when compiled and run? #include #include using namespace std; int main() { int V = 3; vector adj; adj[0].push_back(1); return 0; }

A Compilation error: 'push_back' is not a member of 'int'

B Runtime error: Segmentation fault

C Compilation error: cannot subscript a vector<int>

D No error, runs successfully

💡 Hint

Check how adj is declared and used.

adj is a vector, not a vector>. adj[0] returns int&. int has no push_back member, causing compilation error.

❓ Predict Output

advanced

Output after adding edges in directed graph

What is the output of this C++ code printing adjacency list for a directed graph?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int V = 4;
    vector<int> adj[V];
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(2);
    adj[2].push_back(3);

    for (int i = 0; i < V; i++) {
        cout << i << ": ";
        for (auto v : adj[i]) {
            cout << v << " -> ";
        }
        cout << "null" << endl;
    }
    return 0;
}

A

0: 1 -> 2 -> null
1: 2 -> null
2: 3 -> null
3: null

B

0: 1 -> null
1: 2 -> null
2: 3 -> null
3: null

C

0: 1 -> 2 -> 3 -> null
1: 2 -> null
2: 3 -> null
3: null

D

0: null
1: 2 -> null
2: 3 -> null
3: null

💡 Hint

Check which edges are added from each vertex.

Edges added: 0->1, 0->2, 1->2, 2->3. So adjacency list matches option A.

🧠 Conceptual

expert

Memory complexity of adjacency list vs adjacency matrix

For a graph with V vertices and E edges, which statement about memory usage is correct?

A Both adjacency list and adjacency matrix use O(V^2) memory

B Adjacency list uses O(V + E) memory; adjacency matrix uses O(V^2) memory

C Adjacency list uses O(V^2) memory; adjacency matrix uses O(V + E) memory

D Both adjacency list and adjacency matrix use O(V + E) memory

💡 Hint

Think about how edges are stored in each representation.

Adjacency list stores edges only, so O(V + E). Adjacency matrix stores all possible edges, so O(V^2).

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A list storing only isolated vertices

B. A matrix showing connections between all pairs of vertices

C. A list of all edges without vertex information

D. A list where each vertex stores a list of its adjacent vertices

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each vertex and the vertices it connects to directly.

2. Step 2: Compare with other graph representations

   Unlike adjacency matrix, adjacency list focuses on neighbors per vertex, not all pairs.

3. Final Answer:

   A list where each vertex stores a list of its adjacent vertices -> Option D

4. Quick Check:

   Adjacency list = vertex with neighbors [OK]

Hint: Adjacency list = vertex + its neighbors list [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores all edges as pairs only
• Assuming it stores isolated vertices only

2. Which of the following is the correct C++ syntax to declare an adjacency list for a graph with n vertices using vectors?

easy

A. vector<int> adj[n];

B. vector adj(n);

C. vector adj[n];

D. vector<int> adj(n);

Solution

1. Step 1: Understand vector of vectors declaration

   To represent adjacency list, we use vector adj(n); to create n empty lists.

2. Step 2: Check other options for correctness

   vector<int> adj[n]; declares a non-standard variable-length array (VLA) of vectors. vector adj[n]; is invalid syntax. vector<int> adj(n); declares a single vector of ints, not a list of lists.

3. Final Answer:

   vector adj(n); -> Option B

4. Quick Check:

   Use vector of vectors for adjacency list [OK]

Hint: Use vector for adjacency list [OK]

Common Mistakes:

• Using vector<int> adj(n) which is 1D vector
• Incorrect syntax like vector adj[n];
• Confusing array of vectors with vector of vectors

3. What will be the output adjacency list after executing the following C++ code?

int V = 3;
vector adj(V);
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(2);
for(int i = 0; i < V; i++) {
  cout << i << ": ";
  for(auto v : adj[i]) cout << v << " ";
  cout << endl;
}

medium

A. 0: 1 2
1: 2
2:

B. 0: 2 1
1: 2
2:

C. 0: 1
1: 2
2: 0 1

D. 0:
1: 0 2
2: 1

Solution

1. Step 1: Trace adjacency list insertions

   adj[0] gets 1 and 2 pushed, adj[1] gets 2 pushed, adj[2] remains empty.

2. Step 2: Print adjacency list content

   For i=0: prints "0: 1 2 ", for i=1: "1: 2 ", for i=2: "2: " (empty).

3. Final Answer:

   0: 1 2 1: 2 2: -> Option A

4. Quick Check:

   Push_back order preserved in adjacency list [OK]

Hint: Push_back order shows neighbors in insertion order [OK]

Common Mistakes:

• Assuming adjacency list is sorted automatically
• Mixing up indices and values
• Printing empty lists incorrectly

4. Identify the error in the following code snippet that tries to add an edge to an adjacency list for an undirected graph:

int V = 4;
vector adj(V);
int u = 1, v = 3;
adj[u].push_back(v);
// Missing line here

medium

A. The code should also add adj[v].push_back(u) for undirected edge

B. The vector declaration is incorrect

C. The indices u and v are out of range

D. push_back should be replaced with insert

Solution

1. Step 1: Understand undirected graph edge addition

   For undirected graphs, edges must be added both ways: u to v and v to u.

2. Step 2: Check code for missing reverse edge

   Code adds edge from u to v but misses adj[v].push_back(u), so graph is incomplete.

3. Final Answer:

   The code should also add adj[v].push_back(u) for undirected edge -> Option A

4. Quick Check:

   Undirected edge = add both directions [OK]

Hint: Add edges both ways for undirected graphs [OK]

Common Mistakes:

• Adding edge only one way in undirected graph
• Using wrong vector syntax
• Confusing push_back with insert

5. Given a directed graph with 4 vertices and edges: (0->1), (0->2), (1->2), (2->0), (2->3), (3->3), which adjacency list representation correctly shows the graph?

hard

A. 0: 2 1
1: 2
2: 3 0
3: 3

B. 0: 1 2
1: 0 2
2: 0 3
3: 3

C. 0: 1 2
1: 2
2: 0 3
3: 3

D. 0: 1 2
1: 2
2: 3
3: 0 3

Solution

1. Step 1: List edges for each vertex

   Vertex 0 connects to 1 and 2, vertex 1 connects to 2, vertex 2 connects to 0 and 3, vertex 3 connects to itself (3).

2. Step 2: Match edges to adjacency list options

   0: 1 2 1: 2 2: 0 3 3: 3 matches exactly the edges given. Others have wrong order or extra edges.

3. Final Answer:

   0: 1 2 1: 2 2: 0 3 3: 3 -> Option C

4. Quick Check:

   Match edges to adjacency list exactly [OK]

Hint: Write edges per vertex to verify adjacency list [OK]

Common Mistakes:

• Mixing order of neighbors
• Adding edges not in original graph
• Missing self-loop at vertex 3