Cod sursa(job #1709765)

Utilizator pl4y0nHodorogea Alexandru pl4y0n Data 28 mai 2016 13:48:51
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <tuple>
#include <queue>

using namespace std;

vector<vector <int> > graf;
vector<bool> vis;
int nrVertex,nrEdges;

tuple<int,int> bfs(int vert)
{
	if(vert<=0|| vert>nrVertex)
		return tuple<int,int>();
	int element,i=0,last,mDist;
	queue<int> q,dist;
	q.push(vert);
	dist.push(0);
	vis[vert]=true;
	while(!q.empty())
	{
		element=q.front();
		for(i=0;i<graf[element].size();i++)
		{
			if(!vis[graf[element][i]])
			{
				q.push(graf[element][i]);
				dist.push(dist.front()+1);
				vis[graf[element][i]]=true;
			}
		}
		last=q.front();
		mDist = dist.front();
		dist.pop();
		q.pop();
	}
	return make_tuple(last,mDist);
}

int main()
{
    ifstream in("darb.in");
    ofstream out("darb.out");

    in>>nrVertex;

    int x,y;
	while(in>>x)
	{
        in>>y;
        if(graf.size()<max(x,y)+1)
            graf.resize(max(x,y)+1,vector<int>());
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
	vis.resize(graf.size(),0);

	int a=get<0>(bfs(1));
	vis.assign(graf.size(),0);
	int b=get<1>(bfs(a));
	out<<b+1;
	return 0;
}