1 条题解

  • 0
    @ 2022-8-3 13:56:36

    求树的直径,两遍dfs即可

    //蒟蒻的代码
    #include<iostream>
    #include <vector>
    
    using namespace std;
    
    const int N = 10000 + 10;
    
    int n, c, d[N];
    vector<int> e[N];//用vector存储树
    
    void dfs(int u, int fa) {
      for (int v : e[u]) {
        if (v == fa)
          continue;
        d[v] = d[u] + 1;
        if (d[v] > d[c]) 
          c = v;
        dfs(v, u);
      }
    }
    
    int main() {
      scanf("%d", &n);
      //输入
      for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
      }
      //两遍dfs
      dfs(1, 0);
      d[c] = 0;
      dfs(c, 0);
      cout << d[c] << endl;
      return 0;
    }
    
    • 1

    信息

    ID
    406
    时间
    500ms
    内存
    1536MiB
    难度
    9
    标签
    递交数
    18
    已通过
    4
    上传者