Cod sursa(job #1103987)

Utilizator kiralalaChitoraga Dumitru kiralala Data 10 februarie 2014 11:13:15
Problema Diametrul unui arbore Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100005

using namespace std;

FILE* f=freopen("darb.in","r",stdin);
FILE* o=freopen("darb.out","w",stdout);

vector<int> graph[NMAX];
bool vis[NMAX];
int depth[NMAX];

int n,m;
int BFS(int x)
{
    queue<int> q;
    q.push(x);
    vis[x]=1;
    int r;
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        r=x;
        for(int i=0;i<graph[x].size();++i)
        {
            int ind=graph[x][i];
            if(!vis[ind])
            {
                vis[ind]=1;
                q.push(ind);
            }
        }
    }
    return r;
}
int dmax;
void DFS(int x)
{
    for(int i=0;i<graph[x].size();++i) {
        if(!depth[graph[x][i]])
        {
            depth[graph[x][i]]=depth[x]+1;
            if(depth[graph[x][i]]>dmax) dmax=depth[graph[x][i]];
            DFS(graph[x][i]);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);

    for(int i=0;i<m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    int x=BFS(1);
    depth[x]=1;
    DFS(x);
    printf("%d",dmax);

    return 0;
}