Cod sursa(job #1666663)

Utilizator azbe11Anonim azbe11 Data 28 martie 2016 11:24:19
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

int dfs(const int &vf,const vector<vector<int> > &graph,int &l)
{
    stack<int> s;
    vector<bool> visited;
    visited.resize(graph.size(),false);
    s.push(vf);
    visited[vf]=true;
    int k=0,i,aux,pm=vf;
    bool found;
    while(!s.empty())
    {
        aux=s.top();
        if(k>l)
        {
            pm=aux;
            l=k;
        }
        found=false;
        //cout<<"\nk == "<<k<<"; diam == "<<l<<"\nMa aflu pe nodul "<<aux+1<<'\n';
        for(i=0;i<graph[aux].size() && !found;i++)
        {
            if(!visited[graph[aux][i]])
                found=true;
        }
        if(found)
        {
            //cout<<"Am gasit "<<graph[aux][i-1]+1<<'\n';
            s.push(graph[aux][i-1]);
            visited[graph[aux][i-1]]=true;
            k++;
        }
        else
        {
            s.pop();
            k--;
        }
    }
    return pm;
}

int main()
{
    int n,i,x,y,pmin;
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    fin>>n;
    vector<vector<int> > graph;
    vector<int> grade;
    graph.resize(n);
    grade.resize(n,0);
    for(i=0;i<n-1;i++)
    {
        fin>>x>>y;
        x--; y--;
        graph[x].push_back(y); graph[y].push_back(x);
        grade[x]++; grade[y]++;
        if(grade[x]<grade[pmin]) pmin=x;
        if(grade[y]<grade[pmin]) pmin=y;
    }
    int cent1=-1,cent2=-1,vf1=0,vf2=0,vaux1=0,vaux2=0,diam=0,diaux=0;
    vf1=pmin;
    vf2=dfs(vf1,graph,diam);
    vaux1=vf2;
    vaux2=dfs(vaux1,graph,diaux);
    if(diaux>diam)
    {
        diam=diaux;
        vf1=vaux1;
        vf2=vaux2;
    }
    //cout<<vf1+1<<' '<<vf2+1;
    fout<<diam+1;
    return 0;
}