如何优化邻接表上的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 的问题。问题 link- https://www.codechef.com/problems/FIRESC

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

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

这个解决方案给了我时间限制 exceeded.I 已经看到 C++ 中的其他解决方案被接受了，这些解决方案具有使用向量的完全相同的逻辑，但我现在对 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; 
}

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

How to optimize dfs traversal on an adjacency list?

c

optimization

adjacency-list

depth-first-search

time-limiting