网络寻路

网络寻路

题目

问题分析

思路：从根节点出发找到最深的叶子节点，然后从以该叶子节点为根节点出发找到最深的叶子节点，简言之就是两次深搜

#include#include#define MAX 1000000+10using namespace std;vector M[MAX];int vis[MAX] = {0};int sum = 0;void dfs(int s,int start,int length);int main(){ //图的输入 //freopen("in.txt","r",stdin); int m,n; //节点数目和连接数目 cin >> m >> n; for(int i= 0;i < n;i++) { int x,y; cin >> x >> y; M[x].push_back(y); M[y].push_back(x); } for(int i = 1; i <= m;i++) { //对每个节点都开始遍历 dfs(i,i,0); } cout << sum << endl; return 0;}/* 从一个节点开始，走了三步就count++; 出发节点开始不标记*/void dfs(int s,int start,int length){ //如果走了三步ok if(length==3) { sum++; return ; } int size = M[start].size(); //对节点所有的路径进行遍历 for(int i = 0;i < size;i++) { //如果目前没走两步，当回到目标节点即不可 if(M[start][i]==s&&length!=2) continue; //走过的不用考虑 if(vis[M[start][i]] == 1) continue; //不满足上述情况的 标记走过 vis[M[start][i]] = 1; dfs(s,M[start][i],length+1); //走完标记没走过 vis[M[start][i]] = 0; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。