Cod sursa(job #1261461)

Utilizator vlady1997Vlad Bucur vlady1997 Data 12 noiembrie 2014 13:01:54
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
        #include <cstdio>
        #include <cstring>
        #include <algorithm>
        #include <vector>
        using namespace std;
        vector <int> g[100001];
        int a[100001], dist[100001], sol[100001], q[100001], n;
        bool ok[100001];
        int bfs (int x)
        {
            int i, p=1, u=1, nod, Max=0;
            memset(sol,0,sizeof(sol)); memset(q,0,sizeof(q)); memset(ok,0,sizeof(ok));
            sol[x]=1; q[p]=x; ok[x]=true;
            while (p<=u)
            {
                nod=q[p];
                for (i=0; i<g[nod].size(); i++)
                {
                    if (ok[g[nod][i]]==false)
                    {
                        q[++u]=g[nod][i];
                        ok[g[nod][i]]=true;
                        sol[g[nod][i]]=sol[nod]+1;
                        if (sol[nod]+1>Max) Max=sol[nod]+1;
                    }
                }
                p++;
            }
            return Max;
        }
        int main()
        {
            int m=0, i, j, x, y, Max=0;
            freopen("darb.in","r",stdin);
            freopen("darb.out","w",stdout);
            scanf("%d",&n);
            for (i=1; i<n; i++)
            {
                scanf("%d%d",&x,&y);
                g[x].push_back(y);
                if (x==1) a[++m]=y;
            }
            for (i=1; i<=m; i++)
            {
                dist[i]=bfs(a[i]);
            }
            sort(dist+1,dist+m+1);
            if (m==1) Max=n;
            else Max=dist[m-1]+dist[m]+1;
            printf("%d",Max);
            fclose(stdin);
            fclose(stdout);
            return 0;
        }