fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<stdbool.h>
  4. #define MAX_VERTICES 8
  5.  
  6. //Node structure for adjacency list
  7. struct Node{
  8.     int vertex;
  9.     struct Node* next;
  10. };
  11.  
  12. // Graph structure using adjacency list
  13. struct Graph{
  14.     struct Node* adjlist[MAX_VERTICES];
  15.     int numVertices;
  16. };
  17.  
  18. // Edge structure to store edges during DFS
  19. struct Edge{
  20.     int u,v;
  21. };
  22.  
  23. //Function to create a new node
  24. struct Node* createNode (int v){
  25.     struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
  26.     newNode ->vertex = v;
  27.     newNode->next = NULL;
  28.     return newNode;
  29. }
  30.  
  31. // Function to initilize the graph
  32. void initGraph (struct Graph* graph, int vertices){
  33.     graph->numVertices=vertices;
  34.     for(int i=0; i< vertices; i++) {
  35.         graph->adjlist [i] = NULL;
  36. }
  37. }
  38.  
  39. // Function to add an edge to the graph (undirected) 
  40. void addEdge (struct Graph* graph, int u, int v){
  41.     // Add edge from u to v
  42.     struct Node* newNode = createNode(v);
  43.     newNode->next = graph->adjlist[u];
  44.     graph->adjlist[u] = newNode;
  45.     // Add edge from v to u (since undirected)
  46.     newNode = createNode(u);
  47.     newNode->next = graph->adjlist[v];
  48.     graph->adjlist [v] = newNode;
  49. }
  50.  
  51. //DFS function to find articulation points and biconnected components
  52. void DFS (struct Graph* graph, int u, int parent, int* disc, int* low, int* parentArray, bool* articulation, struct Edge* stack, int* stackTop, int* bccCount
  53. ){
  54.     static int time = 0;
  55.     int children = 0;
  56.     disc [u] = low [u]= ++time; // Set discovery time and low value
  57.     // Traverse all adjacency vertices of u
  58.     struct Node* temp=graph->adjlist[u];
  59.     while(temp){
  60.         int v=temp->vertex;
  61.         if (disc[v]==-1){ //is not visited yel
  62.         children++;
  63.         parentArray[v] = u;
  64.         // push edge (u,v) to stack
  65.         stack[(*stackTop)++] = (struct Edge){u,v};
  66.         //Recur for the child vertex
  67.         DFS (graph, v, u, disc, low, parentArray, articulation,stack, stackTop,bccCount);
  68.         //Check if the subtree rooted at v has a back Connection to an ancestor of u
  69.         low[u]=(low[u]<low [v])? low[u]: low[v];
  70.         //If u is root and has more than one child, its an anticulation point
  71.  
  72.         if(parent == -1&&children >1)
  73.         articulation[u] = true;
  74.         //If u is not root and low value of one of it's child is more than or equal to u's discovery time 
  75.         if (parent!=-1&& low[v]>=disc[u]){
  76.             articulation [u] = true;
  77.             //u is an articulation point, print the edges forming the biconnected component
  78.             printf("Biconnected component %d \n", ++(*bccCount));
  79.             struct Edge edge;
  80.             do{
  81.                 edge=stack[--(*stackTop)];
  82.                 printf("%d-%d", edge.u, edge.v); 
  83.                 }while(edge.u!= u || edge.v!= v);
  84.                 printf("\n");
  85.         }
  86.                 }else if (v!=parent&& disc[v] < disc[u]){
  87.                     //update low value of u for back edge
  88.                 low[u] = (low [u]<disc[v])? low[u]: disc[v];
  89.                 // Push back edge (u,v) to stack 
  90.                 stack[(*stackTop)++] = (struct Edge){u, v};
  91.             }
  92.         temp = temp->next;
  93.     }
  94. }
  95.  
  96. // Function to find and paint all biconnected components using DFS
  97.  
  98. void findBCC(struct Graph* graph){
  99. int V= graph->numVertices;
  100. int disc[MAX_VERTICES], low[MAX_VERTICES], parentArray[MAX_VERTICES];
  101. bool articulation [MAX_VERTICES];
  102. struct Edge stack[MAX_VERTICES*MAX_VERTICES];
  103. //Stack to store edges
  104. int stackTop=0, bccCount=0;
  105. // Initilize discovery and low values
  106. for(int i=0; i<V;i++){
  107. disc[i]=-1;
  108. low[i]=-1;
  109. parentArray[i] =-1;
  110. articulation[i] = false;
  111. }
  112. //Perform DFS traversal for each component
  113. for (int i=0; i<V; i++){
  114. if(disc[i] == -1){
  115.     DFS(graph, i,-1, disc, low, parentArray, articulation, stack,&stackTop,&bccCount);
  116. }
  117. }
  118. // Print articulation points
  119. printf("Articulation points: \n");
  120. for (int i=0; i<V; i++){
  121. if (articulation[i]){
  122. printf("%d",i);
  123. }
  124. }
  125. printf("\n");
  126. }
  127.  
  128. int main(){
  129. // Initialize the graph with 8 vertices
  130. int vertices = 8;
  131. struct Graph graph;
  132. initGraph(&graph,vertices);
  133. //Add edges to the graph (undirected)
  134. addEdge(&graph, 0, 1);
  135. addEdge(&graph, 0,2);
  136. addEdge(&graph, 1, 2);
  137. addEdge(&graph, 1, 3);
  138. addEdge(&graph, 1, 4);
  139. addEdge(&graph, 3, 4);
  140. addEdge(&graph, 3,5);
  141. addEdge(&graph,4,5);
  142. addEdge(&graph, 5,6);
  143. addEdge(&graph, 5,7);
  144. // Display the adjacency list representation of the graph
  145. printf("Graph Representation (Adjacency list): \n");
  146. for(int i=0; i<vertices; i++){
  147. struct Node* temp =graph.adjlist[i];
  148. printf("Vertex %d: ", i);
  149. while (temp){
  150. printf("%d->", temp->vertex);
  151. temp = temp->next;
  152. }
  153. printf("NULL \n");
  154. }
  155. // Find and print biconnected components and articulation points
  156. findBCC(&graph);
  157. return 0;
  158. }
Success #stdin #stdout 0s 5272KB
comments (?)
stdin
copy 
45
stdout
copy 
Graph Representation (Adjacency list): 
Vertex 0: 2->1->NULL 
Vertex 1: 4->3->2->0->NULL 
Vertex 2: 1->0->NULL 
Vertex 3: 5->4->1->NULL 
Vertex 4: 5->3->1->NULL 
Vertex 5: 7->6->4->3->NULL 
Vertex 6: 5->NULL 
Vertex 7: 5->NULL 
Biconnected component 1 
5-7
Biconnected component 2 
5-6
Biconnected component 3 
3-13-45-34-51-4
Articulation points: 
15
https://ideone.com/IVZnX3
language:
C++14 (gcc 8.3)
created:
78 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!