How to optimize dfs traversal on an adjacency list?

Question

//dfs traversal using adjacency list
#include <stdio.h>
#include <malloc.h>
#define gc getchar_unlocked
#define MOD 1000000007
int visited[100000];
long long int capt=0;
struct node 
{
    int vertex;
    struct node *next;
};
struct node *adj[100000];
inline int read_int()  //fast input function
{
    char c = gc();
    while(c<'0' || c>'9') 
        c = gc();
    int ret = 0;
    while(c>='0' && c<='9') 
    {
        ret = 10 * ret + c - '0';
        c = gc();
    }
    return ret;
}
void insert(int x,int y)  //function to add a node to the adjacency list
{
    struct node *new,*last;
    new=(struct node*)malloc(sizeof(struct node));
    new->vertex=y;
    new->next=NULL;
    if(adj[x]==NULL)
        adj[x]=new;
    else
    {
        last=adj[x];
        while(last->next!=NULL)
            last=last->next;
        last->next=new;
    }
}
void dfs(int v)    //simple dfs function,capt variable stores no. of
{                  //nodes in each connected component
    struct node *ptr;
    ptr=adj[v];
    visited[v]=1;
    capt++;
    while(ptr!=NULL)
    {
        v=ptr->vertex;
        if(!visited[v])
            dfs(v);
        ptr=ptr->next;
    }
}
int main()
{
    int t,n,m,x,y,i,comp=0;
    long long int ans;
    struct node *ptr;
    t=read_int();
    while(t--)
    {
        n=read_int();   // no of nodes is n and m is no of edges of
        m=read_int();   //undirected graph
        ans=1;
        comp=0;
        for(i=1;i<=n;i++)
        {
            adj[i]=NULL;
            visited[i]=0;
        }
        for(i=0;i<m;i++)
        {
            x=read_int();   //takes in on edge at a time of undirected graph 
            y=read_int();
            insert(x,y);   
            insert(y,x);
        }
        for(i=1;i<=n;i++)
        {
            if(!visited[i])
            {
                dfs(i);
                ans*=capt;   
                if(ans>=MOD)
                    ans%=MOD;
                capt=0;
                comp++; //no of connected components
            }
        }
        printf("%d %lld\n",comp,ans);
    }
    return 0;
}

So I have been getting time limit exceeded for this problem called fire escape routes on codechef. Problem link- https://www.codechef.com/problems/FIRESC

Basically the problem is to find the no of connected components in the graph and no of ways of choosing a one node from each connected component,which is equal to the product of the no of nodes in each connected components in the graph.

Eg: {1,2,3} and {3,4} no of ways of choosing one node is 3*2=6

This solution is giving me time limit exceeded.I have seen other solutions in C++ with exactly same logic using vector get accepted,but I am not comfortable with C++ as of now. Please help me with further optimization of this code to get this solution accepted! :-)

Answer 1

You could of course just insert the new node at the beginning of the list instead of appending it since the order of edges in the adjacency list doesnt matter. In C++ it would be:

void insert(int x, int y)  
{
    node *xnode = new node;
    xnode->vertex = v;
    xnode->next = adj[x]; // either its null or is pointing to a node already
    adj[x] = xnode; 
}

Answer 2

I submitted the answer on the Codechef site and it got accepted and the reason for slowing of your code is:

Every time you insert you have to go through entire linked list of corresponding vertex

So the trick is to keep a pointer to the last node of every vertex linked list.

First declare an array of pointers to hold the last pointers.

struct node *last[100000];

Now modify your insert function as:

void insert(int x,int y)  //function to add a node to the adjacency list
{
    struct node *new,*last;
    new=(struct node*)malloc(sizeof(struct node));
    new->vertex=y;
    new->next=NULL;
    if(adj[x]==NULL)
        {
            adj[x]=new;
            last[x]=new;
        }
    else
    {
        last[x]->next=new;
        last[x]=new;
    }
}