Cod sursa(job #2204745)

Utilizator MrRobotMrRobot MrRobot Data 16 mai 2018 22:55:39
Problema Diametrul unui arbore Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

vector <list <int> > graf;
vector <bool> viz;

void DFS(int nod, int depth, int &max_depth, int &node_depth)
{
    viz[nod] = true;
    int i;
    //cout<<"nod= "<<nod<<endl;
    for(auto i: graf[nod])
    {
        if(viz[i] == false)
        {
            //cout<<"i= "<<i<<"   ";
            viz[i] = true;
            depth++;
            //cout<<"depth= "<<depth<<endl;
            if(depth > max_depth)
            {
                max_depth = depth;
                node_depth = i;
            }
            DFS(i, depth, max_depth, node_depth);
        }
    }

}



int main()
{
    int n;
    fin>>n;
    int a, b;
    graf.resize(n+1);
    while(fin>>a)
    {
        fin>>b;
        graf[a].push_back(b);
        //cout<<a<<" "<<b<<endl;
        graf[b].push_back(a);
    }
    viz.resize(n+1);
    int depth=0, max_depth=0, node_depth=1, temp;
    DFS(1, depth, max_depth, node_depth);
    viz.clear();
    viz.resize(n+1);
    DFS(node_depth, depth, max_depth, temp);
    fout<<max_depth;

}