Cod sursa(job #1880646)

Utilizator FlowstaticBejan Irina Flowstatic Data 15 februarie 2017 20:50:16
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#define NMAX 100005
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");

vector<int> G[NMAX];
queue<int> Q;
int viz[NMAX], dis[NMAX], diam,last,N;

void bfs(int x);

int main()
{
    fin>>N;
    int x,y;
    for(int i = 1; i<=N;i++)
    {
        fin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    bfs(1);
    bfs(last);
    fout<<diam<<'\n';
    return 0;
}

void bfs(int x)
{
    memset(viz,0,sizeof(viz));
    memset(dis,0,sizeof(dis));
    Q.push(x);
    viz[x] = 1;
    dis[x] = 1;

    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        for(int i = 0; i<G[nod].size();i++)
            if(!viz[G[nod][i]])
        {
            viz[G[nod][i]]=1;
            dis[G[nod][i]] = dis[nod] +1;
            Q.push(G[nod][i]);

            diam = dis[G[nod][i]];
            last = G[nod][i];
        }
    }
}