1 
//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++ 中的其他解决方案使用向量的逻辑完全相同，但我现在对 C++ 不满意。请帮助我进一步优化此代码以使此解决方案被接受！:-)

4

2 回答 2

2

我在 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;
    }
}
于 2015-07-17T13:06:21.800 回答
0

您当然可以只在列表的开头插入新节点而不是附加它，因为邻接列表中边的顺序无关紧要。在 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; 
}
于 2018-09-02T04:02:44.620 回答