#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// Function to add an edge to the graph
void addEdge(int graph[MAX_VERTICES][MAX_VERTICES], int start, int end) {
graph[start][end] = 1;
graph[end][start] = 1;
}
// Recursive function to perform DFS and check for cycles
int isCyclicUtil(int graph[MAX_VERTICES][MAX_VERTICES], int currentVertex, int parent, int visited[MAX_VERTICES]) {
visited[currentVertex] = 1;
int i;
for ( i = 0; i < MAX_VERTICES; i++) {
if (graph[currentVertex][i]) {
if (!visited[i]) {
if (isCyclicUtil(graph, i, currentVertex, visited))
return 1;
} else if (i != parent) {
return 1;
}
}
}
return 0;
}
// Function to check whether a graph contains a cycle
int isCyclic(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
int visited[MAX_VERTICES] = {0};
int i;
for (i = 0; i < vertices; i++) {
if (!visited[i]) {
if (isCyclicUtil(graph, i, -1, visited))
return 1;
}
}
return 0;
}
int main() {
int vertices, edges;
int graph[MAX_VERTICES][MAX_VERTICES] = {0};
// Input the number of vertices
printf("Input the number of vertices: ");
scanf("%d", &vertices);
// Input the number of edges
printf("Input the number of edges: ");
scanf("%d", &edges);
// Input edges and construct the adjacency matrix
for (int i = 0; i < edges; i++) {
int start, end;
printf("Input edge %d (start end): ", i + 1);
scanf("%d %d", &start, &end);
addEdge(graph, start, end);
}
// Check if the graph contains a cycle
if (isCyclic(graph, vertices))
printf("The graph contains a cycle.\n");
else
printf("The graph does not contain a cycle.\n");
return 0;
}
Output 1
Input the number of vertices: 4
Input the number of edges: 4
Input edge 1 (start end): 0 1
Input edge 2 (start end): 1 2
Input edge 3 (start end): 2 3
Input edge 4 (start end): 3 0
The graph contains a cycle.
=== Code Execution Successful ===
Output2
Input the number of vertices: 4
Input the number of edges:
3
Input edge 1 (start end): 0 1
Input edge 2 (start end): 1 2
Input edge 3 (start end): 2 3
The graph does not contain a cycle.
0 Comments