幅優先探索 aoj grl_5_a 木の直径

GRL_5_a 木の直径

GRL_5_a 木の直径
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A

解説

木の直径とは、重みを考慮して最も遠い頂点間の距離である.
適当な頂点を選んでそこから最も遠い頂点を選ぶ.
そこをさらに出発点としたときの最も遠い頂点との距離が直径に等しい.

出発点からの距離の計算には幅優先探索を用いる.

計算量

$O(V)$

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#define N_MAX 100001

typedef struct Edge { Int v, w; }Edge;

Int N;
Int d[N_MAX];
vector<Edge> edges[N_MAX];


Int bfs(Int u) {
    loop(i,0,N) {
        d[i] = -1;
    }

    queue<Int> Q;

    Q.push(u);
    d[u] = 0;

    while (!Q.empty()) {
        Int parent = Q.front(); Q.pop();
        for (auto child: edges[parent]) {
            if (d[child.v] != -1) continue;
            Q.push(child.v);
            d[child.v] = d[parent] + child.w;
        }
    }

    Int maxIndex = 0;
    loop(i,1,N) {
      if (d[maxIndex] < d[i]) maxIndex = i;
    }

    return maxIndex;
}


Int diametar() {
  Int u = bfs(0);
  Int v = bfs(u);
  return d[v];
}

int main(void) {
  Int u, v, w;
  cin >> N;
  while (cin >> u >> v >> w) {
    edges[u].push_back({v, w});
    edges[v].push_back({u, w});
  }

  cout << diametar() << endl;
}