Pagini recente » Cod sursa (job #3172244) | Cod sursa (job #1299488) | Cod sursa (job #181097) | Cod sursa (job #872604) | Cod sursa (job #1546914)
#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;
}