Cod sursa(job #2610541)

Utilizator cristi1616Olaru Cristian cristi1616 Data 4 mai 2020 23:51:08
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100009
#define kInf (1 << 30)

class Task {
public:
  void solve() {
    read_input();
    print_output(get_result());
  }

private:
  int n, m, source;;
  vector<int> adj[NMAX];
  vector<int> d;

  void read_input() {
  	ifstream fin("darb.in");
    fin >> n;
    d.resize(n + 1);
    for (int i = 1; i < n; ++i) {
      int x, y;
      fin >> x >> y;
      adj[x].push_back(y);
      adj[y].push_back(x);
    }
    fin.close();
  }

  int get_result() {
    bfs(1);
    int max = 1, dmax = d[1];
    for (int i = 2; i <= n; ++i) {
      if (d[i] > dmax && d[i] != kInf) {
        max = i;
        dmax = d[i];
      }
    }
    bfs(max);
    max = 1;
    dmax = d[1];
    for (int i = 2; i <= n; ++i) {
      if (d[i] > dmax && d[i] != kInf) {
        max = i;
        dmax = d[i];
      }
    }
    return dmax;
  }

  void bfs(int source) {
  	queue<int> Q;
  	for (int i = 1; i <= n; ++i) {
      d[i] = kInf;
    }
    Q.push(source);
    d[source] = 0;
    while (!Q.empty()) {
      int node = Q.front();
      Q.pop();
      for (auto &it : adj[node]) {
        if (d[node] + 1 < d[it]) {
          d[it] = d[node] + 1;
          Q.push(it);
        }
      }
    }
  }

  void print_output(int result) {
  	ofstream fout("darb.out");
    fout << result + 1 << "\n";
  	fout.close();
  }
};

int main() {
  Task *task = new Task();
  task->solve();
  delete task;
  return 0;
}