c - 如何优化邻接表上的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 上遇到了这个名为 fire escape routes 的问题。 问题链接- https://www.codechef.com/problems/FIRESC

基本上，问题是找到图中连通分量的数量和从每个连通分量中选择一个节点的方法的数量，它等于图中每个连通分量的节点数量的乘积。

例如: {1,2,3} 和 {3,4} 选择一个节点的方式有3*2=6

这个解决方案超出了我的时间限制。我已经看到 C++ 中的其他解决方案使用 vector 的逻辑完全相同，但我现在对 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;
    }
}