#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Graph structure
struct Node {
int vertex;
struct Node* next;
};
struct Node* adj[MAX]; // Adjacency list
int visited[MAX], disc[MAX], low[MAX], parent[MAX];
int time = 0;
// Stack to store edges
struct Edge {
int u, v;
} stack[MAX];
int top = -1;
// Add edge to the stack
void push(int u, int v) {
stack[++top].u = u;
stack[top].v = v;
}
// Pop and print one biconnected component
void printComponent(int u, int v) {
printf("Biconnected Component: ");
while (top >= 0) {
int x = stack[top].u;
int y = stack[top].v;
top--;
printf("(%d-%d) ", x, y);
if ((x == u && y == v) || (x == v && y == u)) break;
}
printf("\n");
}
// Add edge in adjacency list
void addEdge(int u, int v) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = adj[u];
adj[u] = newNode;
}
// DFS to find biconnected components
void DFS(int u) {
visited[u] = 1;
disc[u] = low[u] = ++time;
struct Node* temp = adj[u];
while (temp != NULL) {
int v = temp->vertex;
if (!visited[v]) {
parent[v] = u;
push(u, v);
DFS(v);
low[u] = (low[u] < low[v]) ? low[u] : low[v];
if (low[v] >= disc[u]) {
printComponent(u, v);
}
} else if (v != parent[u] && disc[v] < disc[u]) {
low[u] = (low[u] < disc[v]) ? low[u] : disc[v];
push(u, v);
}
temp = temp->next;
}
}
// Driver Code
int main() {
int vertices = 5;
int edges[][2] = {
{0, 1}, {1, 2}, {2, 0},
{1, 3}, {1, 4}
};
int edgeCount = sizeof(edges) / sizeof(edges[0]);
// Build the graph
for (int i = 0; i < edgeCount; i++) {
int u = edges[i][0];
int v = edges[i][1];
addEdge(u, v);
addEdge(v, u); // undirected
}
for (int i = 0; i < vertices; i++) {
if (!visited[i]) {
DFS(i);
}
}
return 0;
}
Comments
Post a Comment