Cod sursa(job #1703000)

Utilizator adrian.popoviciPopovici Adrian adrian.popovici Data 15 mai 2016 23:05:16
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

vector <vector <long> > graf;
vector <bool> visited;
long n;

void Citire()
{
    long x,y;
    ifstream f("darb.in");
    f>>n;
    graf.resize(n);
    visited.resize(n,false);
    while (f>>x>>y)
    {
        x--;
        y--;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
}

void ResetViz()
{
    visited.clear();
    visited.empty();
    visited.resize(n, false);
}

void BFS(long x, long &capat)
{
    long i=0;
    vector <long> coada;
    coada.push_back(x);
    visited[x]=true;
    while (i<coada.size())
    {
        for (long j=0;j<graf[coada[i]].size();j++)
        {
            if (!visited[graf[coada[i]][j]])
            {
                coada.push_back(graf[coada[i]][j]);
                visited[graf[coada[i]][j]]=true;
            }
        }
        capat=coada[i];
        i++;
    }
    ResetViz();
    //return dist;
}

void BFS(long x, long y, long &dist )
{
    long i=0;
    bool gasit=false;
    vector <long> coada;
    coada.push_back(x);
    visited[x]=true;
    while (i<coada.size())
    {
        for (long j=0;j<graf[coada[i]].size();j++)
        {
            if (!visited[graf[coada[i]][j]])
            {
                if (graf[coada[i]][j]==y)
                {
                    dist++;
                    return;
                }
                coada.push_back(graf[coada[i]][j]);
                visited[graf[coada[i]][j]]=true;
            }
        }
        i++;dist++;
    }
    ResetViz();
}

int main()
{
    Citire();
    long c1,c2,dist=0;
    BFS(0,c1);
    BFS(c1,c2);
    BFS(c1,c2,dist);
    ofstream g("darb.out");
    g<<dist<<" ";
    g.close();
    return 0;
}