//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 %lldn",comp,ans);
}
return 0;
}
所以我得到的时间限制已经超过了这个问题,叫做codechef上的防火通道。问题链接- https://www.codechef.com/problems/FIRESC
基本上,问题是找出图中连通组件的个数,以及从每个连通组件中选择一个节点的方法的个数,该节点等于图中每个连通组件的节点个数的乘积
如:{1,2,3}和{3,4}3*2=6
这个解决方案超出了我的时间限制。我已经看到了c++中使用vector的完全相同逻辑的其他解决方案被接受,但我现在对c++不太满意。请帮助我进一步优化这个代码,以获得这个解决方案接受!: -)
我在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;
}
}
你当然可以在列表的开头插入新节点,而不是附加它,因为邻接表中边的顺序无关紧要。在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;
}