Cod sursa(job #1100146)

Utilizator gabrielvGabriel Vanca gabrielv Data 6 februarie 2014 17:46:54
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 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];

bool OK;
bool Gebraucht[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 Tiefe)
{
    Gebraucht[Knoten] = !OK;
    Abstand[Knoten] = maxim(Abstand[Knoten], Tiefe);
    LetztenKnoten = Knoten;
    Die_Losung = maxim(Die_Losung, Abstand[Knoten]);

    for(vector < int > :: iterator it = G[Knoten].begin(); it != G[Knoten].end(); ++ it)
        if(Gebraucht[*it] == OK)
            DFS(*it, Abstand[Knoten] + 1);
}

void Losen()
{
    OK = false;
    DFS(1,0);

    OK = true;
    DFS(LetztenKnoten,0);
}

void Drucken()
{
    freopen("darb.out","w",stdout);

    printf("%d\n",Die_Losung);
}

int main()
{
    Scannen();
    Losen();
    Drucken();
    return 0;
}