Как оптимизировать обход 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; 
} 

Таким образом, я превысил предельный срок для этой проблемы, называемой маршрутами эвакуации на кодеке. Проблемы ссылка- 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; 
    } 
}