Cod sursa(job #1761745)

Utilizator dranoellenTurica Leonard-Petru dranoellen Data 22 septembrie 2016 20:10:05
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
vector<int> muc[100003];
vector <int>::iterator it;
stack <int> st;
int use[100003],n;
int main()
{
    ifstream fin ("darb.in");
    ofstream fout ("darb.out");
    fin>>n;
    int i=0,x,y;
    while(i<n-1)
    {
        fin>>x>>y;
        muc[x].push_back(y);
        muc[y].push_back(x);
        ++i;
    }


    st.push(1);
    int depth=1,depthit=1;
    while(!st.empty())
    {
        x=st.top();
        st.pop();
        it=muc[x].begin();
        while(it!=muc[x].end())
        {
            if(!use[*it])
            {
                st.push(*it);
                use[*it]=use[x]+1;
                if(depth<use[*it])
                    depth=use[*it],depthit=*it;
            }
            ++it;
        }
    }
    memset(use,0,sizeof(use));
    st.push(depthit);
    use[depthit]=1;
    while(!st.empty())
    {
        x=st.top();
        st.pop();
        it=muc[x].begin();
        while(it!=muc[x].end())
        {
            if(!use[*it])
            {
                st.push(*it);
                use[*it]=use[x]+1;
                if(depth<use[*it])
                    depth=use[*it];
            }
            ++it;
        }
    }
    fout<<depth;

    return 0;
}