DAG

#include <stdio.h>

#include <stdlib.h>

#define MAX_NODES 100

// Graph structure

typedef struct Node

{

int vertex;

struct Node *next;

} Node;

Node *adjList[MAX_NODES]; // Adjacency list

int vis[MAX_NODES] = {0}; // Visited array

int pathVis[MAX_NODES] = {0}; // Path visited array

// Function to add an edge

void addEdge(int src, int dest)

{

Node *newNode = (Node *)malloc(sizeof(Node));

newNode->vertex = dest;

newNode->next = adjList[src];

adjList[src] = newNode;

}

// DFS function to detect cycles

int dfsCheck(int node)

{

vis[node] = pathVis[node] = 1;

for (Node *temp = adjList[node]; temp; temp = temp->next)

{

if (!vis[temp->vertex] && dfsCheck(temp->vertex))

return 1;

else if (pathVis[temp->vertex])

return 1;

}

pathVis[node] = 0;

return 0;

}

// Function to check if graph is cyclic

int isCyclic(int vertices)

{

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

{

if (!vis[i] && dfsCheck(i))

return 1;

}

return 0;

}

int main()

{

int vertices, edges, src, dest;

printf("Enter number of vertices: ");

scanf("%d", &vertices);

printf("Enter number of edges: ");

scanf("%d", &edges);

// Initialize adjacency list

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

adjList[i] = NULL;

printf("Enter edges (source destination):\n");

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

{

scanf("%d %d", &src, &dest);

addEdge(src, dest);

}

if (isCyclic(vertices))

printf("The graph contains a cycle and is NOT a DAG.\n");

else

printf("The graph is a DAG (Directed Acyclic Graph).\n");

return 0;

}