比如我们要对一棵有根树进行 DFS,使用邻接表 vector
存储树,像这样:
vector<int>v[100005];//存树
int d[100005];//深度
void DFS(int u,int fa,int dep){
d[u]=dep;
for(int i=0,s=v[u].size();i<s;i++){
if(v[u][i]==fa)continue;
DFS(v[u][i],u,dep+1);
}
}
那么,5-8 行应该可以换成:
if(!v[u].empty()){
for(vector<int>::iterator it=v[u].begin();it!=v[u].end();it++){
if(*it==fa)continue;
DFS(*it,u,dep+1);
}
}
请问这两种哪个快啊QAQ