# C-Program For Finding The Strongly Connected Component of a Directed Graph (The Tarjan’s Algorithm)

Rating 2.33 out of 5
[?]

Hi All. This is the program used to find the strongly connected components using DFS algorithm also called Tarjan’s Algorithm. One of my friend had a problem in the code so though of typing it.

``` // Strongly connected components using DFS technique // Anshuman Pandey 11/08```
``` #include <stdio.h> #include <stdlib.h>```

``` #define WHITE 0 #define GRAY 1 #define BLACK 2 int n;  // number of nodes int e;  // number of edges struct edge { int tail,head,type; }; typedef struct edge edgeType; edgeType *edgeTab; int *firstEdge;  // Table indicating first in range of edges with a common tail int vertexStatus,secondDFSrestarts; int tailThenHead(const void* xin, const void* yin) // Used in calls to qsort() and bsearch() for read_input_file() { int result; edgeType x,y; x=(edgeType) xin; y=(edgeType) yin; result=x->tail - y->tail; if (result!=0) return result; else return x->head - y->head; } void read_input_file() { int a,b,i,j; edgeType work; edgeType ptr; printf("Enter number of vertices,edges"); scanf("%d %d",&n,&e); edgeTab=(edgeType) malloc(e*sizeof(edgeType)); if (!edgeTab) { printf("edgeTab malloc failed %dn",LINE); exit(0); } // read edges for (i=0; i<e; i++) { printf("If a--->b then enter a,b: "); scanf("%d %d",&a,&b); if (a<0 || a>=n || b<0 || b>=n) { printf("Invalid input %d %d at %dn",a,b,LINE); exit(0); } edgeTab[i].tail=a; edgeTab[i].head=b; } // sort edges qsort(edgeTab,e,sizeof(edgeType),tailThenHead); // Coalesce duplicates into a single edge j=0; for (i=1; i<e; i++) if (edgeTab[j].tail==edgeTab[i].tail && edgeTab[j].head==edgeTab[i].head) ; else { j++; edgeTab[j].tail=edgeTab[i].tail; edgeTab[j].head=edgeTab[i].head; } e=j+1; // For each vertex as a tail, determine first in range of edgeTab entries firstEdge=(int) malloc((n+1)sizeof(int)); if (!firstEdge) { printf("malloc failed %dn",LINE); exit(0); } j=0; for (i=0; i<n; i++) { firstEdge[i]=j; for ( ; j<e && edgeTab[j].tail==i; j++) ; } firstEdge[n]=e; } int finishIndex; void DFSvisit(int u) { int i,v; vertexStatus[u]=GRAY; for (i=firstEdge[u];i<firstEdge[u+1];i++) { v=edgeTab[i].head; if (vertexStatus[v]==WHITE) DFSvisit(v); } vertexStatus[u]=BLACK; secondDFSrestarts[--finishIndex]=u; } void reverseEdges() { int a,b,i,j; edgeType work; edgeType *ptr; for (i=0; i<e; i++) { a=edgeTab[i].tail; b=edgeTab[i].head; edgeTab[i].tail=b; edgeTab[i].head=a; } // sort edges qsort(edgeTab,e,sizeof(edgeType),tailThenHead); // For each vertex as a tail, determine first in range of edgeTab entries if (!firstEdge) { printf("malloc failed %dn",LINE); exit(0); } j=0; for (i=0; i<n; i++) { firstEdge[i]=j; for ( ; j<e && edgeTab[j].tail==i; j++) ; } firstEdge[n]=e; } void DFSvisit2(int u) { int i,v; printf("%dn",u); // Indicate that u is in SCC for this restart vertexStatus[u]=GRAY; for (i=firstEdge[u];i<firstEdge[u+1];i++) { v=edgeTab[i].head; if (vertexStatus[v]==WHITE) DFSvisit2(v); } vertexStatus[u]=BLACK; } int main() { int u,i,j,k,nextDFS; int SCCcount=0; read_input_file(); vertexStatus=(int) malloc(nsizeof(int)); secondDFSrestarts=(int) malloc(nsizeof(int)); if (!vertexStatus || !secondDFSrestarts) { printf("malloc failedn"); exit(0); } // DFS code for (u=0;u<n;u++) vertexStatus[u]=WHITE; finishIndex=n; for (u=0;u<n;u++) if (vertexStatus[u]==WHITE) DFSvisit(u); reverseEdges(); // DFS code for (u=0;u<n;u++) vertexStatus[u]=WHITE; for (i=0;i<n;i++) if (vertexStatus[secondDFSrestarts[i]]==WHITE) { SCCcount++; printf("Strongly Connected Component %dn",SCCcount); DFSvisit2(secondDFSrestarts[i]); } ```

```free(edgeTab); free(firstEdge); free(vertexStatus); free(secondDFSrestarts); return 0; } ``` Computer Engineer ... MBA .. Endurance Runner ... Physics Geek ... Genius

1. guess who Believe me.. This code is really useful.. especially bcoz in spite of searching for a looonnngg time I could not find the code on the Internet

2. yoosef please example input file and out put.

• anshumanpandey just try executing the program. it’ll ask for what is required.

3. yoosef please example input file and out put. i am try no generate exe file .

4. Rasheed Hi, it is really a good work. Typing the values for vertices and edges would be so crucial, if the network (graph) is so large. Hence, it would be helpful to the people, if the values can be supplied through a file.

5. eklavya plz……………..give this program in a simple coding

6. in given code there is a function calling of qsort().where is that function…below to that function some for loop is missing….

• anshumanpandey it is a built in function

7. pallavi the program is only taking inputs and NOT displaying any output

8. Indigo This code is USELESS because its not inside Code HTML Tag. If we copy paste this into codeblocks, it will give /223 /224 /226 error codes. As the charecters like “” are encoded. Cannot copy from “viewsource” either because of stupid HTML tags.

• Anshuman Hahaha.. I agree.. It’s been long I coded this piece. The tags did have some issue. Not sure if it works now. Else do the hard way 🙁

This site uses Akismet to reduce spam. Learn how your comment data is processed.