Cod sursa(job #1470452)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 11 august 2015 11:54:31
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define NMAX 100007
FILE *fin, *fout;
using namespace std;
int n, x, y, qu[NMAX], st = 1, dr = 1, sze, tmp, step[NMAX];
char viz[NMAX];
vector<int> adj[NMAX];
int main()
{
    fin = freopen("darb.in", "r", stdin);
    fout = freopen("darb.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i< n; ++i)
    {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    qu[1] = 1;
    viz[1] = 1;
    for(int i = st; i<= dr; ++i)
    {
        sze = adj[qu[i]].size();
        for(int j = 0; j< sze; ++j)
        {
            if(viz[adj[qu[i]][j]] == 0)
            {
                dr++;
                qu[dr] = adj[qu[i]][j];
                viz[adj[qu[i]][j]] = 1;
            }
        }
    }
    tmp = qu[dr];
    memset(viz, 0, sizeof(viz));
    st = 1;
    dr = 1;
    viz[tmp] = 1;
    qu[1] = tmp;
    step[1] = 1;
    for(int i = st; i<= dr; ++i)
    {
        sze = adj[qu[i]].size();
        for(int j = 0; j< sze; ++j)
        {
            if(viz[adj[qu[i]][j]] == 0)
            {
                dr++;
                step[dr] = step[i] + 1;
                qu[dr] = adj[qu[i]][j];
                viz[adj[qu[i]][j]] = 1;
            }
        }
    }
    printf("%d\n", step[dr]);
    fclose(fin);
    fclose(fout);
    return 0;
}