Cod sursa(job #3041388)

Utilizator iraresmihaiiordache rares mihai iraresmihai Data 31 martie 2023 13:45:19
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <vector>

#define MAXN 100000
#define MAX_LOG 20
using namespace std;

struct node{
  bool visited;
  int dist;
  vector <int> neighbours;
};

node tree[MAXN];
int maxDist, nod;
int n;

void dfs(int pos) {
  tree[pos].visited = true;

  if ( maxDist < tree[pos].dist ) {
    maxDist = tree[pos].dist;
    nod = pos;
  }

  for ( int v : tree[pos].neighbours ) {
    if ( !tree[v].visited ) {
      tree[v].dist = tree[pos].dist + 1;
      dfs(v);
    }
  }
}

void reset() {
  int i;

  for ( i = 0; i < n; i++ ) {
    tree[i].visited = false;
    tree[i].dist = 1;
  }
}

void addEdge(int a, int b) {
  tree[a].neighbours.push_back(b);
  tree[b].neighbours.push_back(a);
}

int main() {
  FILE *fin, *fout;
  fin = fopen("darb.in", "r");
  fout = fopen("darb.out", "w");

  int i, a, b;

  fscanf(fin, "%d", &n);

  for ( i = 0; i < n - 1; i++ ) {
    fscanf(fin, "%d%d", &a, &b);
    a--;
    b--;

    addEdge(a, b);
  }


  reset();
  maxDist = -1;
  dfs(0);
  reset();
  dfs(nod);

  fprintf(fout, "%d\n", maxDist);

  fclose(fin);
  fclose(fout);

  return 0;
}