Cod sursa(job #1131640)

Utilizator gabrielvGabriel Vanca gabrielv Data 28 februarie 2014 22:48:01
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <vector>
 
using namespace std;
 
#define NMAX 100010
#define maxim(a,b) ((a>b)?(a):(b))
 
int N;
int LetztenKnoten;
int Die_Losung;
 
int Abstand[NMAX];
 
vector < int > G[NMAX];
 
void Scannen()
{
    freopen("darb.in","r",stdin);
 
    scanf("%d",&N);
 
    for(int i=1,x,y;i<N;i++)
    {
        scanf("%d%d",&x,&y);
 
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
 
void DFS(int Knoten, int Vater)
{
    Abstand[Knoten] = Abstand[Vater] + 1;
 
    if(Abstand[Knoten] > Abstand[LetztenKnoten])
        LetztenKnoten = Knoten;
 
    for(vector < int > :: iterator it = G[Knoten].begin(); it != G[Knoten].end(); ++ it)
        if(*it != Vater)
            DFS(*it, Knoten);
}
 
void Losen()
{
    DFS(1,0);
 
    DFS(LetztenKnoten,0);
 
    Die_Losung = Abstand[LetztenKnoten];
}
 
void Drucken()
{
    freopen("darb.out","w",stdout);
 
    printf("%d\n",Die_Losung);
}
 
int main()
{
    Scannen();
    Losen();
    Drucken();
    return 0;
}