本文共 459 字，大约阅读时间需要 1 分钟。

//起点是s,edges[s]存储的是pair
   
    ,表示s能到达的点以及边权重//下面的做法nodes是存储当前连通块,sum存储的是权重之和//那么这里sum返回值要除以2，因为每条边算了两次//基本原理是:先标记每一个点访问过了并把其加入到nodes存储起来,然后遍历他能到达的//每一个结点加到sum里面去,然后在dfs没有访问过的结点。这样就不重不漏的把每个边算//了两次,这是一种非常保险的算法,可以规避掉很多坑(比如重边与环的情况等)int dfs(string s,vector
    
      &nodes,int &sum){
       st[s] = true;    nodes.push_back(s);    for(auto item : edges[s]){
           sum +=item.second;        if(!st[item.first]) dfs(item.first,nodes,sum);    }    return sum;}
    
   

转载地址：http://rllzi.baihongyu.com/