Cod sursa(job #2019495)

Utilizator Horia14Horia Banciu Horia14 Data 7 septembrie 2017 22:14:58
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include<cstdio>
#include<vector>
#include<queue>
#define MAX_N 100000
using namespace std;

vector<int>G[MAX_N+1];
int dist[MAX_N+1], n, last, diameter;

void Read()
{
    int x, y;
    FILE *fin = fopen("darb.in","r");
    fscanf(fin,"%d",&n);
    for(int i=1; i<=n; i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    fclose(fin);
}

void BFS(int source)
{
    vector<int>::iterator it;
    queue<int>Q;
    int node;
    for(node=1; node <=n; node++)
        dist[node] = 0;
    dist[source] = 1;
    Q.push(source);
    while(!Q.empty())
    {
        node = Q.front();
        Q.pop();
        for(it = G[node].begin(); it != G[node].end(); it++)
            if(!dist[*it])
            {
                dist[*it] = 1 + dist[node];
                Q.push(*it);
                diameter = dist[*it];
                last = *it;
            }
    }
}

int main()
{
    FILE *fout = fopen("darb.out","w");
    Read();
    BFS(1);
    BFS(last);
    fprintf(fout,"%d\n",diameter);
    fclose(fout);
    return 0;
}