Cod sursa(job #1121349)

Utilizator PatrikStepan Patrik Patrik Data 25 februarie 2014 12:34:36
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<cstring>
    using namespace std;
    #define MAX 100001
    #define pb push_back
    int N  , maxx , d[MAX] , poz ;
    vector<int> G[MAX] ;
    bool u[MAX];
    queue<int> Q;

    void read();
    void BFS(int nod);

    int main()
    {
        read();
        BFS(1);
        for(int i = 1 ; i<= N ; ++i )
        if(d[i] > maxx){maxx = d[i];poz = i;}
        memset(d,0,sizeof(d));
        memset(u,0,sizeof(u));
        BFS(poz);
        for(int i = 1 ; i<= N ; ++i )
            if(d[i] > maxx)maxx = d[i];
        freopen("darb.out" , "w" , stdout );
        printf("%d" , maxx + 1 );
        return 0;
    }

    void read()
    {
        int x , y;
        freopen("darb.in" , "r" , stdin );
        scanf("%d" , &N);
        for(int i = 1 ; i< N ; ++i )
        {
            scanf("%d%d" , &x , &y );
            G[x].pb(y);
            G[y].pb(x);
        }
    }

    void BFS(int nod)
    {
        Q.push(nod);
        u[nod] = 1;
        while(!Q.empty())
        {
            int k = Q.front();
            Q.pop();
            for(int j = 0 ; j <(int)G[k].size() ; ++j )
                if(!u[G[k][j]])
            {
                u[G[k][j]] = 1;
                Q.push(G[k][j]);
                d[G[k][j]] = d[k]+1;
            }
        }
    }