Cod sursa(job #2204748)

Utilizator MrRobotMrRobot MrRobot Data 16 mai 2018 23:02:35
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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;
    if(depth > max_depth)
    {
        max_depth = depth;
        node_depth = nod;
    }
    int i;
    //cout<<"nod= "<<nod<<endl;
    for(auto i: graf[nod])
    {
        if(viz[i] == false)
        {
            //cout<<"i= "<<i<<"   ";
            viz[i] = true;
            //cout<<"depth= "<<depth<<endl;

            DFS(i, depth+1, 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=1, max_depth=1, 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;

}