Cod sursa(job #1546914)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 8 decembrie 2015 20:38:44
Problema Diametrul unui arbore Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.2 kb
#include <stdio.h>
#define MAXN 31622

char inc[MAXN][MAXN]; /// matrice de incidenta
int dist[MAXN]; /// distanta pentru DFS

void clean ( int n ) {
  int i;
  for ( i = 0; i < n; i++ )
    dist[i] = -1;
}

void runNode ( int i, int n, int cnt ) {
  int j;
  for ( j = 0; j < n; j++ )
    if ( inc[i][j] == 1 && dist[j] == -1 ) {
      dist[j] = cnt;
      runNode ( j, n, cnt + 1 );
    }
}

int main () {
  FILE *fin, *fout;

  fin = fopen ( "darb.in", "r" );
  fout = fopen ( "darb.out", "w" );

  int n;

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

  int i, a, b;

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

  /// fac DFS din frunze
  int max = -1, j, cnt, lmax;

  for ( i = 0; i < n; i++ ) {
    cnt = 0;
    for ( j = 0; j < n; j++ )
      cnt += ( inc[i][j] == 1 );

    if ( cnt == 1 ) { /// nod terminal
      clean ( n );
      dist[i] = 0;
      runNode ( i, n, 1 );
      /// vad maximul
      lmax = -1;
      for ( j = 0; j < n; j++ )
        if ( dist[j] > max )
          max = dist[j];
    }
  }

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

  fclose ( fin );
  fclose ( fout );

  return 0;
}