云浅知处 @ 2020-10-25 18:43:20
比如我们要对一棵有根树进行 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
by Ryo_Yamada @ 2020-10-25 18:46:28
萌新觉得下面的快(
by BeyondHeaven @ 2020-10-25 18:50:28
你都用 卡常建议数组模拟链表 vector了还关心常数
by Ryo_Yamada @ 2020-10-25 18:57:09
你都用 vector 了还关心常数
by Ryo_Yamada @ 2020-10-25 18:57:41
不过 srz 的 vector 跑的飞快,不知道怎么回事
by Lice @ 2020-10-25 18:57:58
快不快不清楚,只是觉得迭代器比较自然。。?
但是如果带边权之类的话并且你这样写:
vector<int> G[N];
vector<int> W[N];
迭代器就不得不搞两个,下标就只要一个 i。
不过如果你写 vector<pair<int, int> > 或 vector<Edge> 就无所谓