这个不能在函数内将标记解除,需要在函数调用完后统一解除标记。
例如以下代码不合法:
void f(int x){
vis[x]=1;
node[x]++;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].v;
if(!vis[v])f(v);
}
vis[x]=0;
}
...
for(int i=1;i<=k;i++){
f(cow[i]);
}
需要修改为:
void f(int x){
vis[x]=1;
node[x]++;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].v;
if(!vis[v])f(v);
}
}
...
for(int i=1;i<=k;i++){
f(cow[i]);
memset(vis,0,sizeof(vis));
}
相关解释:
因为在边数大于点数的图中,对于从 A 走到 B 这种问题,具有多种路径,但是题目仅要求求解能够走到的点的个数,故只需要求解能否走到(即仅要求走到一次即可),而在函数内部解除标记,则有可能多次走到,极大提高了时间复杂度。