//DEPTH FIRST SEARCH
#include <stdio.h>
#define MAX 20
int stack[MAX];
int top = -1;
void push(int item) {
 if (top == MAX - 1)
 printf("Stack Overflow\n");
 else {
 top++;
 stack[top] = item;
 }
}
int pop() {
 int item;
 if (top == -1) {
 printf("Stack Underflow\n");
 return -1;
 } else {
 item = stack[top];
 top--;
 return item;
 }
}
int isEmpty() {
 if (top == -1)
 return 1;
 else
 return 0;
}
void dfs(int adj_matrix[][MAX], int visited[], int start, int n) {
 int i, current;
 push(start);
 visited[start] = 1;
 while (!isEmpty()) {
 current = pop();
 printf("%d ", current + 1); // Printing vertex numbers (assuming vertices are numbered from 1 to
n)
 for (i = 0; i < n; i++) {
 if (adj_matrix[current][i] == 1 && !visited[i]) {
 push(i);
 visited[i] = 1;
 }
 }
 }
}
int main() {
 int adj_matrix[MAX][MAX], visited[MAX];
 int n, i, j, start_vertex;
 printf("Enter the number of vertices: ");
 scanf("%d", &n);
 printf("Enter the adjacency matrix (1 for edge, 0 otherwise):\n");
 for (i = 0; i < n; i++) {
 for (j = 0; j < n; j++) {
 printf("Is there an edge between vertex %d and vertex %d? (1/0): ", i + 1, j + 1);
 scanf("%d", &adj_matrix[i][j]);
 }
 }
 for (i = 0; i < n; i++)
 visited[i] = 0;
 printf("Enter the starting vertex: ");
 scanf("%d", &start_vertex);
 printf("DFS Traversal: ");
 dfs(adj_matrix, visited, start_vertex - 1, n); // Adjusting the vertex index to 0-based
 return 0;
}