Find strongly connected components, given a list of edges in a graph

scc.c

/* -.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.

 * File Name : SCC.c

 * Purpose : Find strongly connected components (SCCs) in directed graphs

 * Creation Date : 12-03-2012

 * Last Modified : Mon Mar 12 23:36:16 EET 2012

 * Created By : Vasilis Gerakaris <[email protected]>

 _._._._._._._._._._._._._._._._._._._._._.*/

#include <stdio.h>
#include <stdlib.h>

#define unvisited 0
#define underExp 1
#define explored 2

#define BSIZE 1<<15

char buffer[BSIZE];
long bpos = 0L, bsize = 0L;

long readLong()
{
	long d = 0L, x = 0L;
	char c;

	while (1)  {
		if (bpos >= bsize) {
			bpos = 0;
			if (feof(stdin)) return x;
			bsize = fread(buffer, 1, BSIZE, stdin);
		}
		c = buffer[bpos++];
		if (c >= '0' && c <= '9') { x = x*10 + (c-'0'); d = 1; }
		else if (d == 1) return x;
	}
	return -1;
}

long int n;  // nodes
long int e;  // edges

struct edge {
    long int tail,head,type;
};
typedef struct edge edgeType;
edgeType *edgeTab;

long int *firstEdge;  // First edge in range with a common tail

long int *vertexStatus, *secondDFSrestarts;

int tailThenHead(const void* xin, const void* yin)
    // Used in qsort() and bsearch()
{
    long 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 inputScan()
{
    long int a, b, i, j;
    edgeType work;
    edgeType *ptr;

    /* Read number of V and E */
    n = readLong();
    e = readLong();
    edgeTab = (edgeType*) malloc(e * sizeof(edgeType));

    /* Read Edges */
    for (i = 0; i < e; ++i)
    {
        //node A, node B
        a = readLong();
        b = readLong();
        edgeTab[i].tail = a;
        edgeTab[i].head = b;
    }

    /* Sort */
    qsort(edgeTab, e, sizeof(edgeType), tailThenHead);

    // Remove duplicate edges
    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;

    /* Foreach tail V, find 1st edgeTab in range */
    firstEdge = (long int*) malloc( (n + 1) * sizeof(long int));
    j = 0;
    for (i = 0; i < n; ++i)
    {
        firstEdge[i] = j;
        for ( ; j < e && edgeTab[j].tail == i; j++)
            ;
    }
    firstEdge[n] = e;
}

long int finishIndex;

void DFS1(long int u)
{
    long int i, v;

    vertexStatus[u] = underExp;

    for (i = firstEdge[u]; i < firstEdge[u+1]; ++i)
    {
        v = edgeTab[i].head;
        if (vertexStatus[v] == unvisited)
            DFS1(v);
    }
    vertexStatus[u] = explored;
    secondDFSrestarts[ --finishIndex] = u;
}

/* Reverse the direction of edges */
void reverseEdges()
{
    long 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;
    }

    qsort(edgeTab, e, sizeof(edgeType), tailThenHead);

    /* For each tail V, find first edgeTab */
    j = 0;
    for (i = 0; i < n; ++i)
    {
        firstEdge[i] = j;
        for ( ; j < e && edgeTab[j].tail == i; ++j)
            ;
    }
    firstEdge[n] = e;
}

void DFS2(long int u)
{
    long int i, v;

    //printf("%ld \n", u); // u is in Strongly Connected Component
    vertexStatus[u] = underExp;

    for (i = firstEdge[u]; i < firstEdge[u+1]; ++i)
    {
        v = edgeTab[i].head;
        if (vertexStatus[v] == unvisited)
            DFS2(v);
    }
    vertexStatus[u] = explored;
}

int main()
{
    long int u, i, j, k, nextDFS;
    long int SCCcount = 0;

    inputScan();

    vertexStatus = (long int*) malloc(n * sizeof(long int));
    secondDFSrestarts = (long int*) malloc(n * sizeof(long int));
    /* DFS */
    for (u = 0; u < n; ++u)
        vertexStatus[u] = unvisited;
    finishIndex = n;
    for (u = 0; u < n; ++u)
        if (vertexStatus[u] == unvisited)
            DFS1(u);

    reverseEdges();

    /* DFS part */
    for (u = 0; u < n; ++u)
        vertexStatus[u] = unvisited;
    for (i = 0; i < n; ++i)
        if (vertexStatus[secondDFSrestarts[i]] == unvisited)
        {
            SCCcount++;
            //printf("Strongly Connected Component %ld \n", SCCcount);
            DFS2(secondDFSrestarts[i]);
        }

    return 0;
}