Pagini recente » Borderou de evaluare (job #1037436) | Cod sursa (job #429635) | numinum | Cod sursa (job #1703000)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
vector <vector <long> > graf;
vector <bool> visited;
long n;
void Citire()
{
long x,y;
ifstream f("darb.in");
f>>n;
graf.resize(n);
visited.resize(n,false);
while (f>>x>>y)
{
x--;
y--;
graf[x].push_back(y);
graf[y].push_back(x);
}
}
void ResetViz()
{
visited.clear();
visited.empty();
visited.resize(n, false);
}
void BFS(long x, long &capat)
{
long i=0;
vector <long> coada;
coada.push_back(x);
visited[x]=true;
while (i<coada.size())
{
for (long j=0;j<graf[coada[i]].size();j++)
{
if (!visited[graf[coada[i]][j]])
{
coada.push_back(graf[coada[i]][j]);
visited[graf[coada[i]][j]]=true;
}
}
capat=coada[i];
i++;
}
ResetViz();
//return dist;
}
void BFS(long x, long y, long &dist )
{
long i=0;
bool gasit=false;
vector <long> coada;
coada.push_back(x);
visited[x]=true;
while (i<coada.size())
{
for (long j=0;j<graf[coada[i]].size();j++)
{
if (!visited[graf[coada[i]][j]])
{
if (graf[coada[i]][j]==y)
{
dist++;
return;
}
coada.push_back(graf[coada[i]][j]);
visited[graf[coada[i]][j]]=true;
}
}
i++;dist++;
}
ResetViz();
}
int main()
{
Citire();
long c1,c2,dist=0;
BFS(0,c1);
BFS(c1,c2);
BFS(c1,c2,dist);
ofstream g("darb.out");
g<<dist<<" ";
g.close();
return 0;
}