Cod sursa(job #1761773)

Utilizator cosminmaneaCosmin Manea cosminmanea Data 22 septembrie 2016 20:43:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

vector <int> lv[100001];
queue <int> q;
int n,x,y,marime[100001],ultimul,diametru;
bool used[100001];

void bfs(int start)
{
    memset(marime,0,sizeof(marime));
    memset(used,0,sizeof(used));
    q.push(start);
    marime[start]=1;
    used[start]=1;
    int j,k;
    while (!q.empty())
    {
        k=q.front();
        for (j=0;j<lv[k].size();++j)
        {
            if(!used[lv[k][j]])
            {
                q.push(lv[k][j]);
                marime[lv[k][j]]=marime[k]+1;
                used[lv[k][j]]=1;
                diametru=marime[lv[k][j]];
                ultimul=lv[k][j];
            }
        }
        q.pop();
    }
}

int main()
{
    FILE *f=fopen("darb.in","r");
    FILE *g=fopen("darb.out","w");
    fscanf(f,"%d",&n);
    int i;
    for (i=0;i<n-1;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        lv[x].push_back(y);
        lv[y].push_back(x);
    }
    bfs(1);
    bfs(ultimul);
    fprintf(g,"%d",diametru);
    return 0;
}