Cod sursa(job #1666835)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 28 martie 2016 13:45:15
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>

using namespace std;

ifstream in("darb.in");
ofstream out("darb.out");
const int NMAX = 100001;
int n;
vector<int> muchii[NMAX];
vector<int> stiva;
queue<int> coada;
bitset<NMAX> mark;
int last = 0;
unsigned int best = 0;

void citire()
{
     in>>n;
     int x,y;
     for(int i=1;i<n;i++)
     {
        in>>x>>y;
        muchii[x].push_back(y);
        muchii[y].push_back(x);
     }
     in.close();
}

void bfs(int x)
{
    mark.reset();
    mark.set(x);
    coada.push(x);
    int y;
    while(!coada.empty())
    {
        y = coada.front();
        for(unsigned int i=0;i<muchii[y].size();i++)
            if(!mark.test(muchii[y][i]))
        {
            mark.set(muchii[y][i]);
            coada.push(muchii[y][i]);
            last = muchii[y][i];
        }
        coada.pop();
    }
}

void dfs(int x)
{
    mark.reset();
    mark.set(x);
    stiva.push_back(x);
    int y,ok,target;
    while(!stiva.empty())
    {
        y = stiva.back();
        ok = 0;
        for(unsigned int i=0;i<muchii[y].size();i++)
            if(!mark.test(muchii[y][i]))
            {
                ok = 1;
                target = muchii[y][i];
                break;
            }
        if(ok)
        {
            stiva.push_back(target);
            if(stiva.size() > best)
                best = stiva.size();
            mark.set(target);
        }
        else
            stiva.pop_back();
    }
}

int main()
{
    citire();
    bfs(1);
    dfs(last);
    out<<best<<"\n";
    out.close();
    return 0;
}