1D , 2D Array

1.Write a program that takes an array of integers as input, sorts the numbers in ascending
order using pointers, and then prints the sorted array.

Input Format
The first line of input is an integer, n, representing the number of elements in the array.
The second line of input consists of n space-separated integers, representing the elements of the
array arr[i].
Output Format
The output displays a single line containing the space-separated integers of the sorted array.

#include <stdio.h>
#include<stdlib.h>
// Function to sort the numbers using pointers
void sort(int n, int* ptr)
{
int i, j, t;
// Sort the numbers using pointers
for (i = 0; i < n; i++) {

for (j = i + 1; j < n; j++) {

if (*(ptr + j) < *(ptr + i)) {

t = *(ptr + i);
*(ptr + i) = *(ptr + j);
*(ptr + j) = t;
}
}
}

// print the numbers

for (i = 0; i < n; i++)
printf("%d ", *(ptr + i));
}

// Driver code
int main()
{
int n;
scanf("%d",&n);
int *arr=(int*)malloc(sizeof(int)*n);

for (int i=0;i<n;i++)

{
scanf("%d",arr+i);
}
 sort(n, arr);
return 0;
}

2.Write a program to check if a given Matrix is an Identity Matrix or not using pointers.

Input Format
The first line of the input consists of two integers, n and m representing the order of the matrix.
The next input consists of integers, representing the coefficients of the matrix.
Output Format
The output prints whether the given matrix is an identity matrix or not.

#include <stdio.h>
#include <stdlib.h>

int isIdentity(double *matrix, int rows, int cols)

{
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (i == j && matrix[i * cols + j] != 1.0) {
return 0;
}
if (i != j && matrix[i * cols + j] != 0.0) {
return 0;
}
}
}
return 1;
}

int main()
{
int rows, cols;
scanf("%d %d", &rows, &cols);
double *matrix = (double *)malloc(rows * cols * sizeof(double));

for (int i = 0; i < rows; i++) {

for (int j = 0; j < cols; j++) {
scanf("%lf", &matrix[i * cols + j]);
}
}
int isIden = isIdentity(matrix, rows, cols);

if (isIden) {
printf("Identity matrix");
} else {
 printf("Not an identity matrix");
}
free(matrix);

return 0;
}

Singly Linked List

3.Velu is working on a project that involves managing a singly linked list data structure.
The project requires implementing basic operations on the linked list, including appending
new nodes and deleting the last node from the list.Write a program to achieve the above
objectives.

Example:
Input
10
2 25 15 34 55 73 95 82 52 74

Output
2 25 15 34 55 73 95 82 52

Explanation: The last node of the linked list is 74. Print the list after deleting the last node.

Approach:
To delete the last node of a linked list, find the second last node and make the next pointer of
that node null.
Step-by-step algorithm:
 If the first node is null or there is only one node, then they return null.
 if headNode == null then return null
 if headNode.nextNode == null then free
 head and return null
 Create an extra space secondLast, and traverse the linked list till the second last node.
 while secondLast.nextNode.nextNode != null
secondLast = secondLast.nextNode
 Delete the last node, i.e. the next node of the second last node delete(secondLast.nextNode)
and set the value of the next second-last node to null.

Coding:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int val;
struct Node* next;
};
void append(struct Node** head, int val) {
struct Node* tmp = (struct Node*)malloc(sizeof(struct Node));
 tmp->val = val;
tmp->next = NULL;
if (*head == NULL) {
*head = tmp;
} else {
struct Node* curr = *head;
while (curr->next != NULL) {
curr = curr->next;
}
curr->next = tmp;
}
}
void print(struct Node* head) {
if (head == NULL) {
return;
}
struct Node* curr = head;
while (curr != NULL) {
printf("%d ", curr->val);
curr = curr->next;
}
}
void delete_last(struct Node** head) {
if (*head == NULL || (*head)->next == NULL) {
free(*head);
*head = NULL;
} else {
struct Node* curr = *head;
while (curr->next->next != NULL) {
curr = curr->next;
}
free(curr->next);
curr->next = NULL;
}
}
int main() {
int num_of_nodes, i, val;
scanf("%d", &num_of_nodes);
struct Node* myList = NULL;
for (i = 0; i < num_of_nodes; i++) {
scanf("%d", &val);
append(&myList, val);
}
delete_last(&myList);
print(myList);
return 0;
 }

Doubly Linked List

4.You are tasked with developing an employee record management system for a company.
The system needs to maintain a list of employee records using a doubly linked list. Each
employee is represented by a unique integer ID.Write a program that adds employee
records at the front, traverses the list, and prints the same for each addition of employees
in the list.

#include <stdio.h>
#include <stdlib.h>
struct node {
int info;
struct node* prev, * next;
};

struct node* start = NULL;

void traverse() {
struct node* temp;
temp = start;
while (temp != NULL) {
printf("%d ", temp->info);
temp = temp->next;
}
printf("\n");
}
void insertAtFront(int data) {
struct node* temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
temp->prev = NULL;
temp->next = start;
if (start != NULL)
start->prev = temp;
start = temp;
printf("Node Inserted\n");
}
int main() {
int data;
while (scanf("%d", &data) != EOF) {
insertAtFront(data);
traverse();
}
return 0;
}
Circular Linked List
5. You are given a Circular linked list of N nodes. Write a program to Reverse the elements
in the circular linked list.

Example

Input:
7
99 11 22 33 44 55 66

Output:
66 55 44 33 22 11 99

Explanation:
99 11 22 33 44 55 66 values are inserted in the circular linked list. Reversed values are 66 55 44
33 22 11 99.

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* Head = NULL;
struct Node* reverse(struct Node* head_ref) {
if (head_ref == NULL)
return NULL;
struct Node* prev = NULL;
struct Node* current = head_ref;
struct Node* next;
do {
next = current->next;
current->next = prev;
prev = current;
current = next;
} while (current != head_ref);

head_ref->next = prev;
head_ref = prev;
return head_ref;
}
struct Node* insertNode(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
// if (newNode == NULL) {
// printf("\nMemory Error\n");
// return NULL;
//}
 newNode->data = data;
if (head == NULL) {
newNode->next = newNode;
head = newNode;
} else {
newNode->next = head->next;
head->next = newNode;
}
return head;
}
void displayList(struct Node* head) {
struct Node* current = head;
if (head == NULL) {
printf("Display List is empty\n");
return;
} else {
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
}
}

int main() {
int n, i, val;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &val);
Head = insertNode(Head, val);
}
if (Head != NULL) {
struct Node* temp = Head;
while (temp->next != NULL)
temp = temp->next;
temp->next = Head;
}
Head = reverse(Head);
displayList(Head);
return 0;
}

Stack
6. Rithi is building a simple text editor that allows users to type characters, undo their
typing, and view the current text. She has decided to implement this text editor using an
 array-based stack data structure. She has to develop a basic text editor with the following
features:
1. Type a Character (Push): Users can type a character and add it to the text editor.
2. Undo Typing (Pop): Users can undo their typing by removing the last character they entered
from the editor.
3. View Current Text (Display): Users can view the current text in the editor, which is the
sequence of characters in the buffer.
4. Exit: Users can exit the text editor application.

Write a program that simulates this text editor's undo feature using a character stack and
implements the push, pop, and display operations accordingly.

#include <stdio.h>
#include <stdbool.h>
#define MAX_TEXT_LENGTH 100
char textStack[MAX_TEXT_LENGTH];
int stackTop = -1;
void initialize() {
stackTop = -1;
}
bool isFull() {
return stackTop == MAX_TEXT_LENGTH - 1;
}
bool isEmpty() {
return stackTop == -1;
}
void pushCharacter(char value) {
if (!isFull()) {
textStack[++stackTop] = value;
printf("Typed character: %c\n", value);
}
}
void popCharacter() {
if (!isEmpty()) {
char removed = textStack[stackTop--];
printf("Undo: Removed character %c\n", removed);
} else {
printf("Text editor buffer is empty. Nothing to undo.\n");
}
}
void view() {
if (isEmpty()) {
printf("Text editor buffer is empty.\n");
} else {
printf("Current text: ");
for (int i = stackTop; i >= 0; i--) {
 printf("%c ", textStack[i]);
}
printf("\n");
}
}
int main() {
int choice;
char input;
initialize();
while (true) {
if (scanf("%d", &choice) != 1) {
while (getchar() != '\n');
continue;
}
switch (choice) {
case 1:
scanf(" %c", &input);
pushCharacter(input);
break;
case 2:
popCharacter();
break;
case 3:
view();
break;
case 4:
return 0;
default:
printf("Invalid choice\n");
}
}

return 0;
}

Infix to postfix

7.Tisha wants to learn mathematical expressions and she wants to create a program to
accept multiple infix expressions from the user and convert them into postfix expressions
using a Stack-based algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_EXPR_LEN 100
typedef struct {
 char data[MAX_EXPR_LEN];
int top;
} Stack;
void push(Stack* s, char c) {
if (s->top == MAX_EXPR_LEN - 1) {
printf("Stack overflow\n");
exit(EXIT_FAILURE);
}
s->data[++s->top] = c;
}
char pop(Stack* s) {
if (s->top == -1) {
printf("Stack underflow\n");
exit(EXIT_FAILURE);
}
return s->data[s->top--];
}
char peek(Stack* s) {
if (s->top == -1) {
printf("Stack underflow\n");
exit(EXIT_FAILURE);
}
return s->data[s->top];
}
int is_operator(char c) {
if (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '(' || c == ')') {
return 1;
}
return 0;
}
int precedence(char c) {
if (c == '^') {
return 3;
} else if (c == '*' || c == '/') {
return 2;
} else if (c == '+' || c == '-') {
return 1;
} else {
return 0;
}
}
void infix_to_postfix(char* infix, char* postfix) {
Stack operators = { .top = -1 };
int i, j;
char c;
for (i = 0, j = 0; infix[i] != '\0'; i++) {
 c = infix[i];
if (!is_operator(c)) {
postfix[j++] = c;
} else {
if (c == '(') {
push(&operators, c);
} else if (c == ')') {
while (peek(&operators) != '(') {
postfix[j++] = pop(&operators);
}
pop(&operators);
} else {
while (operators.top != -1 && peek(&operators) != '(' && precedence(c) <=
precedence(peek(&operators))) {
postfix[j++] = pop(&operators);
}
push(&operators, c);
}
}
}
while (operators.top != -1) {
postfix[j++] = pop(&operators);
}
postfix[j] = '\0';
}
int main() {
char infix[MAX_EXPR_LEN], postfix[MAX_EXPR_LEN];
int num_expressions, i;
scanf("%d", &num_expressions);
for (i = 1; i <= num_expressions; i++) {
scanf("%s", infix);
infix_to_postfix(infix, postfix);
printf("Postfix expression %d: %s\n", i, postfix);
}
return 0;
}

Evaluation postfix
8.Raja is working on a programming project that involves evaluating postfix expressions.
He needs a tool that can help him efficiently compute the results of such expressions. Write
a program to help Raja evaluate postfix expressions and get the desired results.

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
 int data[MAX_SIZE];
int top;
};
void initialize(struct Stack* stack) {
stack->top = -1;
}
int isEmpty(struct Stack* stack) {
return (stack->top == -1);
}
void push(struct Stack* stack, int value) {
if (stack->top == MAX_SIZE - 1) {
exit(EXIT_FAILURE);
}
stack->data[++(stack->top)] = value;
}
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
exit(EXIT_FAILURE);
}
return stack->data[(stack->top)--];
}
int evaluatePostfix(char postfix[]) {
struct Stack stack;
initialize(&stack);
int i = 0;
while (postfix[i] != '\0') {
if (postfix[i] >= '0' && postfix[i] <= '9') {
push(&stack, postfix[i] - '0');
} else {
int operand2 = pop(&stack);
int operand1 = pop(&stack);
switch (postfix[i]) {
case '+':
push(&stack, operand1 + operand2);
break;
case '-':
push(&stack, operand1 - operand2);
break;
case '*':
push(&stack, operand1 * operand2);
break;
case '/':
push(&stack, operand1 / operand2);
break;
exit(EXIT_FAILURE);
}
 }
i++;
}
return pop(&stack);
}
int main() {
char postfix[MAX_SIZE];
scanf("%s", postfix);
int result = evaluatePostfix(postfix);
printf("%d", result);
return 0;
}

Reverse Queue
9.You are given a queue of integers. Implement a program to reverse the order of elements
in the given queue using a stack.
#include <stdio.h>
#define MAX_SIZE 100
// Structure for Stack
struct Stack {
int arr[MAX_SIZE];
int top;
};
// Initialize Stack
void initStack(struct Stack* stack) {
stack->top = -1;
}
// Check if Stack is empty
int isEmpty(struct Stack* stack) {
return (stack->top == -1);
}
// Push element onto Stack
void push(struct Stack* stack, int ele) {
if (stack->top < MAX_SIZE - 1) {
stack->arr[++(stack->top)] = ele;
}
}
// Pop element from Stack
int pop(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->arr[(stack->top)--];
}
return -1; // Return -1 if the stack is empty
}
// Structure for Queue
struct Queue {
 int arr[MAX_SIZE];
int front, rear;
};
// Initialize Queue
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
// Check if Queue is empty
int isQueueEmpty(struct Queue* queue) {
return (queue->front == -1);
}
// Enqueue element into Queue
void enqueue(struct Queue* queue, int ele) {
if (queue->front == -1) {
queue->front = 0;
}
if (queue->rear < MAX_SIZE - 1) {
queue->arr[++(queue->rear)] = ele;
}
}
// Dequeue element from Queue
int dequeue(struct Queue* queue) {
if (!isQueueEmpty(queue)) {
int ele = queue->arr[queue->front];
if (queue->front == queue->rear) {
queue->front = queue->rear = -1;
} else {
(queue->front)++;
}
return ele;
}
return -1; // Return -1 if the queue is empty
}
// Reverse the Queue
void reverseQueue(struct Queue* queue) {
struct Stack stack;
initStack(&stack);

while (!isQueueEmpty(queue)) {
push(&stack, dequeue(queue));
}
while (!isEmpty(&stack)) {
enqueue(queue, pop(&stack));
}
}
int main() {
struct Queue queue;
int n, ele;
initQueue(&queue);
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &ele);
enqueue(&queue, ele);
}
reverseQueue(&queue);
while (!isQueueEmpty(&queue)) {
printf("%d ", dequeue(&queue));
}
return 0;
}

Binary Search Tree

10.Your task is to create a program that can determine whether a given array of integers
represents a sorted sequence in non-decreasing order.

Specifically, you need to ascertain if this array could be a valid in-order traversal of a
Binary Search Tree (BST).
#include <stdio.h>
#include <stdbool.h>
#include <climits>
// Function to check if an array represents an inorder traversal of a BST
bool isValidInorder(int arr[], int n) {
// If the array is empty, it is a valid BST
if (n == 0) {
return true;
}
// Initialize the minimum possible value for the root
int min_val = INT_MIN;
// Traverse the array and check if it is in ascending order
for (int i = 0; i < n; i++) {
// If the current element is less than the minimum value, it's not a BST
if (arr[i] < min_val) {
return false;
}
// Update the minimum value
min_val = arr[i];
}
// If the array is in ascending order, it represents an inorder traversal of a BST
return true;
}
int main() {
 int n;
// Read the size of the array
scanf("%d", &n);
int arr[n];
// Read the array elements
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
// Check if the array represents an inorder traversal of a BST
if (isValidInorder(arr, n)) {
printf("Yes\n");
} else {
printf("No\n");
}
return 0;
}
return 0;
}

AVL Tree
11.Rishi is fascinated by data structures and wants to explore the AVL trees. He wants to
implement a program that constructs an AVL tree by inserting a series of keys and then
performs a search operation to check if a specific key exists in the AVL tree.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
struct Node* left;
struct Node* right;
int height;
} Node;
int max(int a, int b) {
return (a > b) ? a : b;
}
Node* createNode(int key) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1;
return newNode;
}
int getHeight(Node* node) {
if (node == NULL) {
return 0;
 }
return node->height;
}
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;

y->left = x;
x->right = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
int getBalance(Node* node) {
if (node == NULL) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
Node* insert(Node* root, int key) {
if (root == NULL) {
return createNode(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
} else {
return root;
}
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
int balance = getBalance(root);
if (balance > 1 && key < root->left->key) {
return rightRotate(root);
}
if (balance > 1 && key > root->left->key) {
root->left = leftRotate(root->left);
 return rightRotate(root);
}
if (balance < -1 && key > root->right->key) {
return leftRotate(root);
}
// Right-Left case
if (balance < -1 && key < root->right->key) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
Node* search(Node* root, int key) {
if (root == NULL || root->key == key) {
return root;
}

if (key < root->key) {

return search(root->left, key);
} else {
return search(root->right, key);
}
}
void freeTree(Node* root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
int main() {
Node* root = NULL;
int key;
while (1) {
scanf("%d", &key);
if (key == -1) {
break;
}
root = insert(root, key);
}
int searchKey;
scanf("%d", &searchKey);
Node* result = search(root, searchKey);
if (result == NULL) {
printf("Key not found in the AVL tree.");
 } else {
printf("Key found in the AVL tree.");
}
freeTree(root);
return 0;
}
Priority Queue
12.In a computing environment, tasks are submitted for execution with varying levels of
priority. The system needs to implement a priority queue to efficiently manage the
execution of tasks based on their priority levels.

Implement a priority queue using a binary heap to handle task scheduling. Each task is
represented by a pair of integers: the task ID and the priority level. Tasks with higher
priority levels should be executed before tasks with lower priority levels.
#include <stdio.h>
#include <stdlib.h>
typedef struct Element {
int data;
int priority;
} Element;
typedef struct {
Element* array;
int capacity;
int size;
} PriorityQueue;
void initialize(PriorityQueue* queue, int capacity) {
queue->array = (Element*)malloc(capacity * sizeof(Element));
queue->capacity = capacity;
queue->size = 0;
}
int isEmpty(PriorityQueue* queue) {
return queue->size == 0;
}
void swap(Element* a, Element* b) {
Element temp = *a;
*a = *b;
*b = temp;
}
void enqueue(PriorityQueue* queue, int data, int priority) {
if (queue->size == queue->capacity) {
// Double the capacity if the queue is full
queue->capacity *= 2;
queue->array = (Element*)realloc(queue->array, queue->capacity * sizeof(Element));
}
// Insert the new element at the end
int index = queue->size;
 queue->array[index].data = data;
queue->array[index].priority = priority;
// Heapify up
while (index > 0 && queue->array[index].priority > queue->array[(index - 1) / 2].priority) {
swap(&queue->array[index], &queue->array[(index - 1) / 2]);
index = (index - 1) / 2;
}
queue->size++;
}
int dequeue(PriorityQueue* queue) {
if (isEmpty(queue)) {
// Return a sentinel value or handle underflow as needed
return -1;
}

// Extract the element with the highest priority (at the root)
int data = queue->array[0].data;
queue->array[0] = queue->array[queue->size - 1];
queue->size--;
// Heapify down
int index = 0;
while (1) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int largest = index;
if (leftChild < queue->size && queue->array[leftChild].priority > queue-
>array[largest].priority) {
largest = leftChild;
}
if (rightChild < queue->size && queue->array[rightChild].priority > queue-
>array[largest].priority) {
largest = rightChild;
}
if (largest != index) {
swap(&queue->array[index], &queue->array[largest]);
index = largest;
} else {
break;
}
}
return data;
}
int main() {
PriorityQueue queue;
initialize(&queue, 10);
int data, priority;
 char choice;
do {
scanf("%d %d", &data, &priority);
enqueue(&queue, data, priority);
scanf(" %c", &choice);
} while (choice == 'y' || choice == 'Y');
while (!isEmpty(&queue)) {
printf("Dequeued element with data: %d\n", dequeue(&queue));
}
free(queue.array);
return 0;
}
BFS
13. You are designing a navigation system for a city with multiple interconnected cities.
The cities are represented as vertices, and the connections between cities are represented as
edges in a graph.

Your task is to implement a program that performs a breadth-first search (BFS) traversal
on the graph, starting from a given source city, and outputs the order in which the cities
are visited.

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

void BFS(int** graph, int numCities, int source) {

bool* visited = (bool*)malloc(numCities * sizeof(bool));
for (int i = 0; i < numCities; i++) {
visited[i] = false;
}

int* queue = (int*)malloc(numCities * sizeof(int));

int front = -1;
int rear = -1;

visited[source] = true;
queue[++rear] = source;

while (front != rear) {

int currentCity = queue[++front];

printf("%d ", currentCity);

for (int i = 0; i < numCities; i++) {

if (graph[currentCity][i] == 1 && !visited[i]) {
visited[i] = true;
 queue[++rear] = i;
}
}
}

free(visited);
free(queue);
}

int main() {
int numCities, numConnections;
scanf("%d %d", &numCities, &numConnections);

int** graph = (int**)malloc(numCities * sizeof(int*));

for (int i = 0; i < numCities; i++) {
graph[i] = (int*)malloc(numCities * sizeof(int));
for (int j = 0; j < numCities; j++) {
graph[i][j] = 0;
}
}

for (int i = 0; i < numConnections; i++) {

int a, b;
scanf("%d %d", &a, &b);
graph[a][b] = 1;
}

int source;
scanf("%d", &source);

BFS(graph, numCities, source);

for (int i = 0; i < numCities; i++) {

free(graph[i]);
}
free(graph);

return 0;
}
DFS
14.Arjun is working on a navigation system for a city that consists of multiple landmarks
connected by roads. Each landmark is represented as a vertex in a directed graph, and the
roads between landmarks are represented as edges in the graph.
Your task is to implement a function that finds all possible routes between a given source
landmark and a destination landmark in the city's road network using a Depth-First
Search (DFS) algorithm.
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
struct Graph {
int V;
int adj[MAX_VERTICES][MAX_VERTICES];
};
void addEdge(struct Graph* graph, int u, int v) {
graph->adj[u][v] = 1;
}
void printAllPathsUtil(struct Graph* graph, int u, int d, bool visited[], int path[], int pathIndex) {
visited[u] = true;
path[pathIndex] = u;
pathIndex++;
if (u == d) {
for (int i = 0; i < pathIndex; i++) {
printf("%d", path[i]);
if (i < pathIndex - 1)
printf(" ");
}
printf("\n");
} else {
for (int i = 0; i < graph->V; i++) {
if (graph->adj[u][i] == 1 && !visited[i]) {
printAllPathsUtil(graph, i, d, visited, path, pathIndex);
}
}
}
pathIndex--;
visited[u] = false;
}
void printAllPaths(struct Graph* graph, int s, int d) {
bool visited[MAX_VERTICES];
int path[MAX_VERTICES];
int pathIndex = 0;
for (int i = 0; i < graph->V; i++) {
visited[i] = false;
}
printAllPathsUtil(graph, s, d, visited, path, pathIndex);
}
int main() {
int V, E;
scanf("%d %d", &V, &E);
 struct Graph g;
g.V = V;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
g.adj[i][j] = 0;
}
}
for (int i = 0; i < E; i++) {
int u, v;
scanf("%d %d", &u, &v);
addEdge(&g, u, v);
}
int s, d;
scanf("%d %d", &s, &d);
printAllPaths(&g, s, d);
return 0;
}