求树中的最长路（*【模板】代码个别地方需要根据情况修改读懂理解后再照搬代码）...-白红宇

求树中的最长路（*【模板】代码个别地方需要根据情况修改读懂理解后再照搬代码）...

阅读量：5122 次

发布时间：2019-06-13

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

两次DFS求树中的最长路。

基于邻接矩阵：

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;bool map[10001][10001];int n;int tail;bool vis[1001];int fa[1001];void DFS_root(int dd){ int i, j; for(i=1; i<=n; i++) { if(vis[i]==false && map[dd][i]==true ) { fa[i]=fa[dd]+1; vis[i]=true; DFS_root(i); } } int len=0; tail=1; for(j=2; j<=n; j++) { if(fa[j]>len) tail=j; } //printf("%d***\n", tail ); return;}int len=0; //记录树中最长的路径长度void DFS_len_tree(int dd){ int i, j; for(i=1; i<=n; i++) { if(vis[i]==false && map[dd][i]==true ) { fa[i]=fa[dd]+1; //由前一个节点的长度+1过来的 vis[i]=true; DFS_len_tree(i); } } len=fa[1]; for(j=2; j<=n; j++) { if(fa[j]>len) len=fa[j]; }}int main(){ int i, j; int u, v; scanf("%d", &n); for(i=0; i<=n; i++ ) { for(j=0; j<=n; j++) { map[i][j]=false; } } //map的初始化 for(i=0; i

基于vector二维模拟邻接表：

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define N 100002using namespace std;vector
            
             q[N];bool vis[N];int fa[N];int n, tail;int ans;void DFS_root(int dd){ int i, j; int len; len=q[dd].size(); for(i=0; i
             
              len) { len=fa[j]; tail=j; } }}void DFS_len_tree(int dd){ int len, i, j; len=q[dd].size(); for(i=0; i
              
               ans ) ans=fa[j]; } printf("%d\n", ans ); return 0;}