UNIT – 4

CONNECTED COMPONENTS – DEFINITION

In graph theory, a Connected Component refers to a subgraph in which:
• Every pair of vertices is connected by a path.
• The subgraph is maximal, meaning you cannot add more vertices without breaking
the connectivity.
Formal Definition
Let G=(V,E) be an undirected graph, where:
• V is the set of vertices (or nodes),
• E is the set of edges (or links between nodes).
A connected component of G is a maximal set of vertices C⊆V such that:
• For every pair of vertices u,v∈C there exists a path from u to v.
• No vertex outside of C is connected to any vertex in C.
Types of Graphs Based on Connected Components

Graph Type Description

Connected Graph Has exactly one connected component (all vertices are connected)
Disconnected Graph Has two or more connected components
Isolated Vertex A vertex with no edges is a connected component of size 1

Example
Given an undirected graph:
There are 2 connected components:
1. {A, B, C, D}
2. {E, F}
• No vertex in component 1 is connected to
any vertex in component 2.
How to Find Connected Components
There are two popular graph traversal algorithms used to identify connected components:
1. Depth-First Search (DFS)
2. Breadth-First Search (BFS)
General Approach:
• Initialize all vertices as unvisited.
 • Traverse the graph using DFS or BFS.
• Every time start a new traversal from an unvisited node and discover a new component.
• Count the number of such traversals — that’s the number of connected components.
Algorithm to find Connected Components
Input:
• An undirected graph G = (V, E)
o V: Set of vertices {0, 1, ..., n-1}
o E: Set of edges
• The graph is typically represented as an adjacency list (adj)
Output:
• Total number of connected components
• Optionally: List of nodes in each component
Depth First Search (DFS) Breadth First Search (BFS)
Step 1: Initialize a visited array of size n to false Step 1: Create a 'visited' array of size n,
visited[i] = false for all i from 0 to n-1 initialized to false
Step 2: Initialize a counter to 0 for connected
Step 2: Initialize a component counter to 0 components
Step 3: For each vertex v in 0 to n-1:
Step 3: For each vertex v in V: If visited[v] == false:
If visited[v] == false: Increment counter
// Start a new DFS from vertex v Create an empty queue
Call DFS(v) Enqueue v and mark visited[v] = true
Increment the component counter While queue is not empty:
Dequeue current vertex u
Step 4: Define DFS(v): For each neighbor of u:
Mark visited[v] = true If neighbor not visited:
For each neighbor u of v: Enqueue neighbor
If visited[u] == false: Mark it as visited
Call DFS(u) // Optional: Print the nodes visited in
this BFS (this is one component)
Step 5: Return the component counter (total Step 4: Return counter as number of connected
number of connected components) components
#include <iostream> #include <iostream>
using namespace std; #include <queue>
#define MAX 100 using namespace std;
int adj[MAX][MAX]; // Adjacency matrix #define MAX 100
bool visited[MAX]; // Visited array int adj[MAX][MAX];// Adjacency matrix
int n; // Number of nodes bool visited[MAX]; // Visited array
void dfs(int node) { int n; // Number of nodes
cout << node << " "; void bfs(int start) {
visited[node] = true; queue<int> q;
for (int i = 0; i < n; i++) { q.push(start);
if (adj[node][i] == 1 && !visited[i]) { visited[start] = true;
dfs(i); while (!q.empty()) {
} int node = q.front(); q.pop();
} cout << node << " ";
} for (int i = 0; i < n; i++) {
int main() { if (adj[node][i] == 1 && !visited[i]) {
int edges; q.push(i);
cout << "Enter number of nodes and edges: "; visited[i] = true;
cin >> n >> edges; }
}
// Initialize }
for (int i = 0; i < n; i++) { }
visited[i] = false; int main() {
for (int j = 0; j < n; j++) int edges;
adj[i][j] = 0; cout << "Enter number of nodes and edges:
} ";
cin >> n >> edges;
cout << "Enter edges (u v):\n"; // Initialize
for (int i = 0; i < edges; i++) { for (int i = 0; i < n; i++) {
int u, v; visited[i] = false;
cin >> u >> v; for (int j = 0; j < n; j++)
adj[u][v] = 1; adj[i][j] = 0;
adj[v][u] = 1; // Because undirected }
} cout << "Enter edges (u v):\n";
for (int i = 0; i < edges; i++) {
cout << "Connected component (DFS): "; int u, v;
dfs(0); // For connected graph, start from 0 cin >> u >> v;
adj[u][v] = 1;
return 0; adj[v][u] = 1; // Because undirected
} }
cout << "Connected component (BFS): ";
bfs(0); // For connected graph, start from 0
return 0;
}
Sample Input
Enter number of nodes and edges: 6 5
Enter edges (u v):
01
12
13
34
45
DFS Output:
Connected component (DFS): 0 1 2 3 4 5
BFS Output:
Connected component (BFS): 0 1 2 3 4 5

BFS Vs DFS for Connected Components

Feature BFS (Breadth-First Search) DFS (Depth-First Search)

Depth-wise (uses stack or
Traversal Order Level by level (uses queue)
recursion)
Stack (implicitly via recursion or
Data Structure Used Queue
explicit stack)
 Visited Node
Yes (boolean array or hash) Yes (boolean array or hash)
Tracking
Shortest Path Yes – finds shortest path in
No – may take longer path
Property unweighted graph
Can use more memory (due to Often uses less memory (due to
Memory Usage
queue growth) recursion stack)
Search Strategy Breadth-first (wide first) Depth-first (deep first)
Component Effective for level-based Effective for full exploration
Discovery discovery from one node
Performance (Time
O(V + E) O(V + E)
Complexity)
- When shortest paths needed- - When paths or all
When to Prefer
Level-based tasks configurations needed
- Shortest path- Web crawling- - Maze solving- Cycle detection-
Common Use Cases
Network search Backtracking

BI-CONNECTED COMPONENTS – DEFINITION

A Bi-Connected Component (or Biconnected Component, BCC) of an undirected graph is
a maximal set of edges such that:
1. The removal of any single vertex (and its incident edges) does not disconnect the
component.
2. In other words, there is no "articulation point" (explained below) within a
biconnected component that can separate it.
Key Terms:

Articulation Point (Cut Vertex):

A vertex in a graph whose removal increases the number of connected components in the
graph.

Biconnected Graph:
A connected undirected graph is biconnected if:
• It has no articulation points.
• There are at least two disjoint paths between every pair of
vertices.
Example
Consider the undirected graph:
The triangle formed by A-B-C-D is biconnected: removing any one
of A, B, or C still keeps the triangle connected.
• Vertex D is an articulation point: removing D disconnects E from the rest of the graph.
 • So, the graph has two biconnected components:
o {A, B, C, D}
o {D, E}
How to Find Biconnected Components?
We use Depth-First Search (DFS) and track:
• Discovery time (first visit)
• Lowest reachable vertex (back edges)

This involves:
• A DFS tree
• A stack to keep track of edges
• Identification of articulation points

The Tarjan’s Algorithm is commonly used to find all BCCs in O(V + E) time.
Properties of Biconnected Components

Property Description
A biconnected component is as large as possible — no
Maximal additional edges or vertices from the graph can be included
without violating biconnectivity.
Removing any one vertex does not disconnect the
No articulation point inside
component.
Articulation points (cut vertices) are common to two or
Multiple components may
more biconnected components, but edges belong to only
share articulation points
one.
Each edge belongs to exactly
Unlike vertices, edges are not shared between components.
one biconnected component
DFS traversal can be used to decompose a graph into
DFS-based decomposition biconnected components using lowpoint values and
discovery times.
During DFS, we can push edges to a stack; when a
Identified using stack component ends, pop until the current edge — this gives one
biconnected component.
Graph with no articulation A connected graph without cut vertices is fully
point is itself biconnected biconnected.
Every cycle in the graph is completely contained within a
Cycle property
single biconnected component.

Diagrammatic Representation of Biconnected Graphs

The image shows an undirected graph divided into four biconnected components, each
distinguished by color and connected via articulation points (nodes that, if removed, would
disconnect the graph).

Component Breakdown:
 Pink Component
• Nodes: 1, 2
• Articulation Point: 2
• Description: Node 1 connects to the rest of the graph only via node 2. If node 2 is
removed, node 1 becomes isolated.

Blue Component
• Nodes: 2, 4, 11
• Articulation Point: 2, 8
• Description: A small component bridging 2 to node 8
via node 11 and 4.

Green Component
• Nodes: 2, 3, 5, 6
• Articulation Point: 2
• Description: A tree-like component connected through
2. Removing node 2 separates this subgraph.

Orange Component (Larger Biconnected Unit)

• Nodes: 8, 9, 10, 12
• Articulation Point: 8
• Description: This is the largest biconnected group with multiple cycles. It remains
connected unless 8 is removed.
Articulation Points (Cut Vertices)
• Node 2: Connects 3 different biconnected blocks.
• Node 8: Bridges the core cyclic component with the upper section (nodes 2, 4, 11).

Key Observations
• Every edge belongs to only one biconnected component.
• Articulation points belong to multiple components.
• Removing articulation points would increase the number of connected components.

CONSTRUCTING BICONNECTED GRAPHS WITH SAMPLE DATA

Algorithm
Input:
• An undirected graph G(V, E) with V vertices and E edges
Output:
• A list of biconnected components, each as a set of edges
• A list of articulation points
Step 1: Initialization
1. Initialize arrays:
o disc[u] = discovery time of vertex u (initially 0)
o low[u] = lowest discovery time reachable from u
o visited[u] = false for all u
2. Initialize:
o time = 0 (global timer for DFS)
o edgeStack = empty stack to store edges during DFS
 o AP = set of articulation points
Step 2: DFS Traversal
3. For each unvisited vertex u, do:
o Call DFS(u, parent = -1)
Step 3: DFS(u, parent)
4. Mark u as visited
5. Set disc[u] = low[u] = ++time
6. Initialize children = 0
7. For each adjacent vertex v of u:
o If v is not visited:
▪ Push edge (u, v) onto edgeStack
▪ Call DFS(v, u)
▪ Increment children++
▪ Update low[u] = min(low[u], low[v])
▪ If:
▪ parent ≠ -1 and low[v] ≥ disc[u], or
▪ parent == -1 and children > 1:
▪ Mark u as articulation point
▪ Pop edges from edgeStack until (u, v) is popped
▪ These form one BCC
o Else if v ≠ parent and disc[v] < disc[u]:
▪ Push edge (u, v) onto edgeStack (back edge)
▪ Update low[u] = min(low[u], disc[v])
Step 4: After DFS(u) Finishes
8. After DFS returns to the main loop:
o If edgeStack is not empty, pop all remaining edges as one last BCC
Step 5: Output
9. Output each BCC as a set of edges
10. Output all articulation points

Example

Consider the graph with edges: (0-1), (0-2), (1-3), (2-3), (3-4), (4-5), (5-3)
Step 1: Start DFS at Node 0
• disc[0] = 1, low[0] = 1
• Move to neighbor 1

Step 2: Visit Node 1

• disc[1] = 2, low[1] = 2
• Edge (0-1) is pushed to stack
• Move to neighbor 3

Step 3: Visit Node 3

• disc[3] = 3, low[3] = 3
• Edge (1-3) is pushed
• Move to neighbor 2

Step 4: Visit Node 2

• disc[2] = 4, low[2] = 4
• Edge (3-2) is pushed
 • 2 connects to 0 (already visited) → back edge → low[2] = min(4, disc[0]) = 1
• Push back edge (2-0)
• Return to node 3 → low[3] = min(3, low[2]) = 1

Step 5: Visit Node 4

• disc[4] = 5, low[4] = 5
• Push (3-4)
• Visit node 5 → disc[5] = 6, low[5] = 6
• Push (4-5)
• 5 connects back to 3 → back edge (5-3) → low[5] = min(6, disc[3]) = 3
• Return to 4 → low[4] = min(5, low[5]) = 3
• Return to 3 → low[3] = min(1, low[4]) = 1

Step 6: Identify BCCs

BCC1:
• When returning from 5 to 4, and low[5] ≥ disc[4], we pop edges:
Output: (4-5), (5-3) → form one BCC

BCC2:
• When returning from 4 to 3, and low[4] ≥ disc[3], we pop:
Output: (3-4) → add to previous or new BCC

BCC3:
• When returning from 2 to 3, and low[2] ≥ disc[3], we pop:
Output: (2-3), (2-0) → new BCC

BCC4:
• When returning from 1 to 3, and low[3] ≥ disc[1], pop:
Output: (1-3) → new BCC

BCC5:
• Returning from 1 to 0, and low[1] ≥ disc[0], pop:
Output: (0-1) → new BCC
Step 7: Identify Articulation Points
• Node 3: removing it disconnects 4, 5
• Node 1: removing it disconnects 0, 3
So, articulation points: 1, 3
Program
#include <iostream> }
#include <cstring> }
using namespace std; void printArticulationPoints(int n) {
#define MAX 10 cout << "\nArticulation Points: ";
int graph[MAX][MAX]; // Adjacency matrix bool found = false;
bool visited[MAX]; for (int i = 0; i < n; i++) {
int disc[MAX], low[MAX], parent[MAX]; if (ap[i]) {
bool ap[MAX]; // Articulation points cout << i << " ";
int timeCounter = 0; found = true;
void initialize(int n) { }
memset(graph, 0, sizeof(graph)); }
memset(visited, false, sizeof(visited)); if (!found) cout << "None";
memset(disc, -1, sizeof(disc)); cout << endl;
memset(low, -1, sizeof(low)); }
memset(parent, -1, sizeof(parent)); bool isBiconnected(int n) {
memset(ap, false, sizeof(ap)); DFS(0, n);
timeCounter = 0; for (int i = 0; i < n; i++)
} if (!visited[i])
void addEdge(int u, int v) { return false;
graph[u][v] = 1; for (int i = 0; i < n; i++)
graph[v][u] = 1; if (ap[i])
} return false;
void DFS(int u, int n) { return true;
visited[u] = true; }
disc[u] = low[u] = ++timeCounter; int main() {
int children = 0; int n = 6;
for (int v = 0; v < n; v++) { initialize(n);
if (graph[u][v]) { // Add edges based on the given diagram
if (!visited[v]) { addEdge(0, 1);
children++; addEdge(0, 2);
parent[v] = u; addEdge(1, 3);
DFS(v, n); addEdge(2, 3);
low[u] = min(low[u], low[v]); addEdge(3, 4);
if (parent[u] == -1 && children > addEdge(4, 5); // dotted edge
1) cout << "Nodes: ";
ap[u] = true; for (int i = 0; i < n; i++) cout << i << " ";
if (parent[u] != -1 && low[v] >= cout << "\nEdges: (undirected)\n";
disc[u]) for (int i = 0; i < n; i++)
ap[u] = true; for (int j = i + 1; j < n; j++)
} if (graph[i][j])
else if (v != parent[u]) { cout << i << " - " << j << "\n";
low[u] = min(low[u], disc[v]); printAdjacencyMatrix(n);
}
} if (isBiconnected(n)) {
} cout << "\nThe graph is
} BICONNECTED.\n";
void printAdjacencyMatrix(int n) { } else {
cout << "\nAdjacency Matrix:\n"; cout << "\nThe graph is NOT
for (int i = 0; i < n; i++) { biconnected.\n";
cout << i << ": "; }
for (int j = 0; j < n; j++) { printArticulationPoints(n);
cout << graph[i][j] << " "; return 0;
} }
cout << endl;
Sample Output:
Nodes: 0 1 2 3 4 5
Edges: (undirected)
0-1
0-2
1-3
2-3
3-4
4-5

Adjacency Matrix:
0: 0 1 1 0 0 0
1: 1 0 0 1 0 0
2: 1 0 0 1 0 0
3: 0 1 1 0 1 0
4: 0 0 0 1 0 1
5: 0 0 0 0 1 0

The graph is NOT biconnected.

Articulation Points: 3 4

DYNAMIC PROGRAMMING
Dynamic Programming (DP) is a method for solving complex problems by breaking them
down into simpler subproblems, solving each only once, and storing their results (usually in
a table or array) to avoid redundant computations.
"Don't solve the same subproblem more than once. Store its result and reuse it."
This is especially useful in problems with overlapping subproblems and optimal
substructure.

When to Use Dynamic Programming

DP is used when:
1. Overlapping Subproblems
o The problem can be broken down into smaller problems that repeat.
o Example: Fibonacci numbers:
fib(n) = fib(n-1) + fib(n-2) — same subproblems occur repeatedly.
2. Optimal Substructure
o The solution to the main problem can be built using solutions of its
subproblems.
o Example: Shortest path, Knapsack, etc.

Two Key Techniques in DP

1. Top-Down (Memoization)
• Solve the problem recursively.
• Store the result of each subproblem in a table (usually an array or map).
• If you need the same subproblem again, reuse the stored value.
• Avoids recomputation.
2. Bottom-Up (Tabulation)
• Solve smallest subproblems first.
• Build the final solution from the bottom up by using a table.
• Usually implemented with loops, not recursion.
• Often more space-efficient.

Example: Fibonacci Numbers

Traditional Recursion Method Dynamic Programming Version (Bottom-Up)

int fib(int n) { int fib(int n) {
if (n <= 1) return n; int dp[n+1];
return fib(n-1) + fib(n-2); dp[0] = 0; dp[1] = 1;
} for (int i = 2; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
Time Complexity: O(2^n) Time Complexity: O(n)
(exponential) Space Complexity: O(n) (can be O(1) with 2
variables)

Common Problems Solved by DP

• Fibonacci sequence
• Factorial (if optimized)
• 0/1 Knapsack Problem
• Longest Common Subsequence (LCS)
• Matrix Chain Multiplication
• Coin Change Problem
• Edit Distance
• Rod Cutting Problem
• Subset Sum Problem

Think of memoization like remembering answers to questions you've already solved in a quiz.
Instead of solving them again, you just look them up in your notes.

BACKTRACKING - DEFINITION
Backtracking is a general algorithmic technique for solving recursive problems by trying
to build a solution incrementally, and removing solutions that fail to satisfy the constraints
of the problem at any point. Backtracking is a form of recursion where we try to solve a
problem by choosing an option at each step, and if it leads to a solution, continue; else,
backtrack (i.e., undo the choice) and try another.

It is used when:
• Need to explore all possible combinations.
• Need to undo or backtrack if a path leads to a dead end.

Working Principle
Backtracking uses a depth-first search (DFS) approach:
 1. Start with an empty solution.
2. Try to add a value that meets constraints.
3. If adding the value leads to a solution, recurse.
4. If not, remove the value (backtrack) and try the next.
5. Repeat until all possibilities are explored.

Backtracking – General Form

Algorithm
1. Define a solution space or state space (usually recursive).
2. Choose a structure to represent the partial solution (e.g., array, string).
3. Start from an empty/initial state.
4. For each step or position in the problem:
a. Make a choice (try a candidate value).
b. Check if the current state is valid (satisfies constraints).
- If valid:
i. Recur to explore further decisions.
- If invalid:
i. Undo the current choice (backtrack).
5. If a complete solution is found, record or print it.
6. Return to the previous decision point and try next possible choice.

Pseudocode

procedure BACKTRACKING(state):
if is_solution(state):
process_solution(state)
return
for each candidate in candidates(state):
if is_valid(candidate, state):
make_move(candidate, state)
BACKTRACKING(state)
undo_move(candidate, state)

Components
Component Description
state The current partial solution or position in the solution space
is_solution() Checks whether the current state is a complete and valid solution
process_solution() Records, displays, or stores the complete solution
candidates() Generates possible next steps or values to try
is_valid() Prunes branches that violate constraints
make_move() Applies the decision/candidate
undo_move() Reverts the decision (important for backtracking)

Example Problems That Use Backtracking:

• N-Queens problem
 • Sudoku solver
• Subset sum
• Permutations and combinations
• Graph coloring

SOLUTION SPACE AND CONSTRAINTS IN BACKTRACKING

Solution Space in Backtracking

The solution space is the set of all possible configurations that can be generated by the
algorithm while trying to solve the problem. Backtracking explores this space partially or fully
depending on the constraints and pruning.

Example: N-Queens (for N = 4)

• Total possible queen placements without constraints: 4^4 = 256
• Actual solution space pruned by constraints (e.g., no two queens attack): much smaller.

In this case, each state in the solution space is:

• A partial or complete placement of queens on the board.

Constraints in Backtracking

Constraints are rules or conditions that each partial solution must satisfy in order to continue
expanding into a valid final solution. There are two types of constraints:

Type Description
Explicit Constraints Must always be satisfied. Eg: no two queens in the same row.

Implicit Constraints Applied during construction to prune invalid partial solutions.

Real-Life Analogy:
Suppose you're choosing a 4-digit PIN.
• Solution space: All 4-digit combinations (0000 to 9999).
• Constraints: PIN must not have repeating digits → prune options like 1123 or 8888.

How Backtracking Uses Them

1. Initial state: Empty or base configuration.
2. Recursive choice: Add a valid element (state transition).
3. Constraint check: If current choice violates constraints:
o Backtrack (discard this path).
4. Continue: Otherwise, recurse deeper.
5. Base case: If goal is reached → record solution.

Visualizing the Solution Space

Imagine a tree:
• Each node = partial solution
• Each edge = a possible decision
 • Pruned branches = invalid paths due to constraints
The goal is to prune as early as possible to avoid unnecessary work.

Example: Sudoku

Solution Space:
• 9×9 grid → 81 cells
• Each cell can be 1-9
→ Total raw combinations: 9^81 (huge!)

Constraints:
• Row: Each digit appears once
• Column: Each digit appears once
• Block (3x3): Each digit appears once
→ Backtracking + constraints drastically cuts down this space.

Backtracking doesn't explore the entire solution space. It only goes deep into branches that are
promising (i.e., obey constraints).

CONTROL ABSTRACTION FOR BACKTRACKING

In the context of algorithms and programming, control abstraction refers to the general
structure or pattern of how a particular class of algorithms (like recursion, iteration, or
backtracking) is implemented. It hides the control flow and emphasizes what to do instead of
how exactly it's controlled.

Control Abstraction for Backtracking

Control abstraction for backtracking is a generalized recursive framework for solving

problems by exploring all possible solutions and pruning those that fail constraints. We write
a general-purpose template to explore options, and insert problem-specific logic inside it.

Key Idea Behind Backtracking:

• Try a possibility
• If it leads to a solution, accept it
• If it doesn’t, backtrack (undo the choice and try something else)

General Control Abstraction for Backtracking

Backtrack(position):
if solution found at this position:
process/print/store solution
else:
for each valid option at this position:
if promising(option):
choose(option)
Backtrack(next position)
undo(option)
Key Components:
Component Purpose
Backtrack(position) Recursive call at current level/position
promising(option) Check if choice follows constraints
choose(option) Make a move or decision
undo(option) Revert the move (backtrack)

Example Problems That Use Control Abstraction for Backtracking:

• N-Queens Problem
• Sudoku Solver
• Maze Solving
• Graph coloring
• Subset / Permutation generation
• Word Search in grid

INTRODUCTION TO 8 QUEENS PROBLEM MEANING, SOLVING THE

8 QUEENS PROBLEM WITH SAMPLE DATA
The 8-Queens Problem is a classic puzzle in computer science and artificial intelligence,
especially known for illustrating backtracking algorithms and constraint satisfaction
problems (CSP).

Problem Statement

Place eight queens on a standard 8×8 chessboard such that no two queens attack each other.

Queens attack:
• Horizontally
• Vertically
• Diagonally (both left and right)

So, the goal is to place one queen in each row in such a way that:
• No two queens share the same column
• No two queens are on the same diagonal

Why Is It Important?
The 8-Queens problem:
• Introduces constraint-based problem solving
• Demonstrates backtracking – a brute-force technique for recursive search
• Lays foundation for solving N-Queens, Sudoku, graph coloring, path finding, etc.

Mathematical Background
• There are 92 possible valid solutions to the 8-queens problem.
• If solutions that are symmetric through rotation/reflection are considered the same, there
are 12 unique solutions.
Solution Approach
The most common approach is backtracking, which works like this:
1. Start placing queens row by row.
2. At each step, try placing a queen in all columns of the current row.
3. If a position is safe, place it and move to the next row.
4. If no column is safe in a row, backtrack to the previous row and try a different position.
5. Repeat until all queens are placed successfully.

Algorithm

Step 1:
Create a one-dimensional array board[8]
→ board[i] = j means a queen is placed at row i and column j.

Step 2:
Define a function isSafe(row, col) that checks:
• If any previously placed queen (in rows 0 to row - 1) is in:
o the same column
o or the same diagonal
for i from 0 to row - 1:
if board[i] == col → same column → return false
if abs(board[i] - col) == abs(i - row) → same diagonal → return false
return true

Step 3:
Define the recursive backtracking function placeQueen(row):
If row == 8:
print the board as a solution
return

For col = 0 to 7:
If isSafe(row, col):
board[row] = col // place queen at (row, col)
placeQueen(row + 1) // move to next row
// Implicit backtrack on returning

Step 4:
Call placeQueen(0) from the main() function to start placing queens from row 0.

Note
• Backtracking automatically removes the queen when returning from recursion.
• You may optionally reset board[row] = -1 during backtrack for clarity.

APPLYING BACKTRACKING TO SOLVE 8 QUEENS PROBLEM

#include <iostream>
#include <cmath>
using namespace std;
#define SIZE 8
int board[SIZE]; // board[i] stores column position of queen in row i
int solutionCount = 0;
// Function to check if placing a queen at (row, col) is safe
bool isSafe(int row, int col) {
for (int i = 0; i < row; i++) {
// Check column and diagonals
if (board[i] == col || abs(board[i] - col) == abs(i - row))
return false;
}
return true;
}
// Function to print the board
void printBoard() {
solutionCount++;
cout << "Solution " << solutionCount << ":\n";
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (board[i] == j)
cout << "Q ";
else
cout << ". ";
}
cout << endl;
}
cout << endl;
}
// Recursive function to place queens row by row
void placeQueen(int row) {
if (row == SIZE) {
printBoard(); // A valid solution is found
return;
}
for (int col = 0; col < SIZE; col++) {
if (isSafe(row, col)) {
board[row] = col; // Place queen
placeQueen(row + 1); // Recur to next row
// No need to undo explicitly; it'll be overwritten
}
}
}
int main() {
cout << "Solving the 8-Queens Problem...\n\n";
placeQueen(0);
cout << "Total solutions found: " << solutionCount << endl;
return 0;
}
Sample Output (First Solution)

INTRODUCTION TO SUM OF SUBSET PROBLEM

The Sum of Subsets problem is a combinatorial and NP-complete problem that asks:
Given a set of positive integers and a target sum, is there a subset of the given set whose
elements sum up exactly to the target?

Problem Statement:
Given:
• A set of n positive integers: S = {s₁, s₂, ..., sₙ}
• A target sum: M
Find:
• One or more subsets of S such that the sum of elements in the subset equals M.

Applications
• It appears in resource allocation, cryptography, combinatorial optimization, and
decision-making.
• It forms the basis for subset-sum variations, including the Knapsack Problem.

Example:
Let S = {3, 34, 4, 12, 5, 2} and M = 9.
Subset {4, 5} sums to 9.
Subset {3, 12} sums to 15 (invalid).

Approaches to Solve:
1. Brute-force / Exhaustive Search:
o Check all 2^n subsets → slow for large n.
2. Backtracking:
o Systematically explore subsets.
o Abandon paths that exceed the target.
3. Dynamic Programming:
o Build a table dp[i][j] indicating if sum j is possible using the first i elements.
4. Bitmasking or Memoization (for optimization):
 o Used for larger datasets in practice.
Constraints:
• Input values must be non-negative integers.
• The set size and target value should be within practical computation limits for brute-
force.
Applications:
• Subset sum cryptosystems (e.g., Merkle-Hellman)
• Partition problems
• Load balancing
• Budget planning

Algorithm
Problem Input:
• A set S[1...n] of positive integers
• A target sum M

Goal:
Find all subsets of S whose sum is exactly equal to M.

Preconditions:
• Sort the set S in ascending order (to optimize early pruning).
• Use a global array x[1...n] to store binary choices:
x[i] = 1 → include S[i],
x[i] = 0 → exclude S[i].

Algorithm: sumOfSubsets(i, sum, r)

Parameters:
• i: current index
• sum: current sum of selected elements
• r: sum of remaining elements

Recursive Steps:
1. If sum == M:
→ Print the current subset (x[1...n])
→ return

2. Else if (i > n or sum > M):

→ return (prune the branch)

3. Else if (sum + S[i] <= M):

→ x[i] = 1 // include S[i]
→ sumOfSubsets(i + 1, sum + S[i], r - S[i])

4. If (sum + r - S[i] >= M):

→ x[i] = 0 // exclude S[i]
→ sumOfSubsets(i + 1, sum, r - S[i])
Time Complexity:
• Worst-case: O(2^n) (all subsets)
• Optimized by pruning with sum > M and sum + r < M
Program
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 100
int S[MAX], x[MAX]; // S = set of numbers, x = decision array
int n, targetSum;
void printSubset() { // Function to print the current subset
cout << "{ ";
for (int i = 0; i < n; i++) {
if (x[i] == 1)
cout << S[i] << " ";
}
cout << "}" << endl;
}
// Recursive Backtracking Function
void sumOfSubsets(int i, int currentSum, int remainingSum) {
if (currentSum == targetSum) {
printSubset();
return;
}
if (i >= n || currentSum > targetSum || currentSum + remainingSum < targetSum)
return; // Prune the branch
x[i] = 1; // Include S[i]
sumOfSubsets(i + 1, currentSum + S[i], remainingSum - S[i]);
// Exclude S[i]
x[i] = 0;
sumOfSubsets(i + 1, currentSum, remainingSum - S[i]);
}
int main() {
// Sample input
cout << "Enter number of elements: ";
cin >> n;
cout << "Enter the elements (positive integers only):\n";
for (int i = 0; i < n; i++)
cin >> S[i];
cout << "Enter the target sum: ";
cin >> targetSum;
sort(S, S + n); // Sort the set for better pruning
int totalSum = 0;
for (int i = 0; i < n; i++)
totalSum += S[i];
cout << "\nSubsets that sum to " << targetSum << ":\n";
sumOfSubsets(0, 0, totalSum);
return 0;
}
Sample Input/Output:
Input:
Enter number of elements: 5
Enter the elements (positive integers only):
34521
Enter the target sum: 6
Output:
Subsets that sum to 6:
{15}
{24}
{123}

Visual Trace
Trace only the key decisions in a subset tree, representing each recursive call as a node:
(i, sum) where:
• i = index in the set
• sum = current sum accumulated
We show (include) and (exclude) paths.

Subsets that lead to sum = 6

Let’s list valid subsets traced from the tree:
Subset Chosen Indices Selected Sum
{1, 2, 3} 0,1,2 6
{1, 5} 0,4 6
{2, 4} 1,3 6
{3, 4} 2,3 7 (invalid)
{2, 3, 1} different order 6
(Only the first three are valid, others are either duplicates or exceed 6)
INTRODUCTION TO GRAPH COLOURING
Graph colouring is a fundamental concept in graph theory that involves assigning colours to
elements of a graph under certain constraints. It has wide applications in areas such as
scheduling, register allocation in compilers, and frequency assignment in mobile networks.

Definition
Graph colouring is the process of assigning colours to the vertices (or edges) of a graph such
that no two adjacent elements share the same colour.

The most common form is:

Vertex Colouring:
Assign colours to vertices such that no two
adjacent vertices (i.e., connected directly by an
edge) have the same colour.

Purpose of Graph Colouring

To minimise the number of colours used while
satisfying the constraints. This minimum number
of colours required is called the chromatic
number of the graph.

Real-world Examples
Application Description
Courses (vertices) that share students (edges) need different
Timetabling/Scheduling
time slots
Map Colouring Countries sharing borders get different colours
In compilers, variables that interfere cannot share the same
Register Allocation
register
Wi-Fi Channel
Neighbouring routers should not use the same frequency
Assignment

Key Terms
Term Explanation
Proper colouring No adjacent vertices share the same colour

Chromatic number (χ) Minimum number of colours needed for a proper colouring

Greedy colouring Simple algorithm that assigns the first available colour
k-Colourable graph Can be coloured using ≤ k colours

Algorithms for Graph Colouring

1. Greedy Algorithm
Assign the lowest possible colour to each vertex one by one. Simple but not optimal.
 2. Backtracking
Try assigning colours recursively, backtracking when a conflict occurs.

3. Welsh–Powell Algorithm
Colour higher degree nodes first — improves greedy method.

4. DSATUR (Degree of Saturation)

Heuristic that selects next vertex based on saturation degree (number of different
colours used on neighbours).

GRAPH COLOURING WITH SAMPLE DATA

#include <iostream>
#define V 4 // Number of vertices
#define MAX_COLOR 3 // Maximum colors allowed
using namespace std;
// Function to print the color assignment
void printSolution(int color[]) {
cout << "Color assignment to vertices:\n";
for (int i = 0; i < V; i++)
cout << "Vertex " << i << " ---> Color " << color[i] << "\n";
}
// Check if the current color assignment is safe for vertex v
bool isSafe(int v, bool graph[V][V], int color[], int c) {
for (int i = 0; i < V; i++)
if (graph[v][i] && color[i] == c)
return false;
return true;
}
// Recursive utility function to solve coloring problem
bool graphColoringUtil(bool graph[V][V], int m, int color[], int v) {
if (v == V)
return true; // All vertices are assigned a color
for (int c = 1; c <= m; c++) {
if (isSafe(v, graph, color, c)) {
color[v] = c;
if (graphColoringUtil(graph, m, color, v + 1))
return true;
color[v] = 0; // backtrack
}
}
return false;
}
// Main function to solve the problem
bool graphColoring(bool graph[V][V], int m) {
int color[V] = {0};
if (!graphColoringUtil(graph, m, color, 0)) {
cout << "Solution does not exist.\n";
 return false;
}
printSolution(color);
return true;
}
// Driver code
int main() {
// Adjacency matrix for the graph
bool graph[V][V] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 1},
{1, 0, 1, 0}
};
int m = MAX_COLOR; // Number of colors
graphColoring(graph, m);
return 0;
}

Sample Input (Adjacency Matrix)

Sample Output:
Color assignment to vertices:
Vertex 0 ---> Color 1
Vertex 1 ---> Color 2
Vertex 2 ---> Color 3
Vertex 3 ---> Color 2

• The algorithm assigns colours recursively and backtracks when it encounters a

conflict.
• The constraint is that no two adjacent vertices can have the same colour.
• We used MAX_COLOR = 3, which was sufficient for this example.