Cod sursa(job #1206782)

Utilizator tdr_drtTdr Drt tdr_drt Data 11 iulie 2014 11:20:37
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
int n,m,i,dim,aux,dis;
vector<int> graf[100100];
bitset<100100>viz;

void read()
{
   f>>n;
   int x,y,i;
   for(i=1;i<n;i++)
   {
       f>>x>>y;
       graf[x].push_back(y);
       graf[y].push_back(x);
   }
}

void dfs1(int nod,int nivel)
{
    if(viz[nod]!=1)
    {
        viz[nod]=1;
        if(nivel>dis) {dis=nivel; aux=nod;}
        for(int i=0;i<graf[nod].size();i++)
        {
            dfs1(graf[nod][i],nivel+1);
        }
    }
}

void dfs2(int nod,int nivel)
{
    if(viz[nod]!=0)
    {
        viz[nod]=0;
        if(nivel>dim) dim=nivel;
        for(int i=0;i<graf[nod].size();i++)
        {
            dfs2(graf[nod][i],nivel+1);
        }
    }
}

void solve()
{
    dfs1(1,0);
    dfs2(aux,1);
}

void write()
{
    g<<dim;
}

int main()
{
    read();
    solve();
    write();

    return 0;
}