如何在邻接列表上优化dfs遍历？

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;
}

所以我已经超出了这个问题的时间限制，称为codechef上的火灾逃生路线。问题链接 - https://www.codechef.com/problems/FIRESC

基本上问题是在图中找不到连接的组件，没有从每个连接的组件中选择一个节点的方法，这等于图中每个连接组件中的节点数的乘积。

例如：{1,2,3}和{3,4}没有选择一个节点的方法是3 * 2 = 6

这个解决方案给了我超出时间限制。我已经看到C ++中的其他解决方案使用vector get接受了完全相同的逻辑，但我现在对C ++不满意。请帮助我进一步优化此代码以接受此解决方案！ :-)

Answer 1

我在Codechef网站上提交了答案并且它已被接受，并且代码放慢的原因是：

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

所以诀窍是保持指向每个顶点链表的最后一个节点的指针。

首先声明一个指针数组来保存最后一个指针。

struct node *last[100000];

现在将您的插入函数修改为：

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;
    }
}

Answer 2

您当然可以在列表的开头插入新节点而不是附加它，因为邻接列表中的边缘顺序无关紧要。在C ++中它将是：

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; 
}