Cod sursa(job #2815823)

Utilizator CalinCruceanu3576Cruceanu CalinCruceanu3576 Data 10 decembrie 2021 14:45:08
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

class Graf
{
private:
  int N, diametru, nodStart;
  vector<vector<int>> adj;
  vector<int> viz;
  void DFS(int, int);

public:
  Graf(int);
  void adaugaMuchie(int, int);
  int Afisare();
};

Graf ::Graf(int n)
{
  N = n;
  adj.resize(n + 1);
  viz.resize(n + 1);
}

void Graf ::adaugaMuchie(int x, int y)
{
  adj[x].push_back(y);
  adj[y].push_back(x);
}

void Graf ::DFS(int x, int d)
{
  if (d > diametru)
  {
    diametru = d;
    nodStart = x;
  }

  viz[x] = 1;
  for (auto i : adj[x])
    if (!viz[i])
      DFS(i, d + 1);
}

int Graf ::Afisare()
{
  int i;
  DFS(1, 1);
  for (i = 0; i < N; i++)
    viz[i] = 0;
  diametru = 0;
  DFS(nodStart, 1);
  return diametru;
}

int main()
{
  int i, x, y, n;
  fin >> n;
  Graf G(n);
  for (i = 1; i <= n; i++)
  {
    fin >> x >> y;
    G.adaugaMuchie(x, y);
  }
  fout << G.Afisare();
  return 0;
}