Pagini recente » Cod sursa (job #1444009) | Cod sursa (job #1968097) | Istoria paginii utilizator/cristinuta19 | Cod sursa (job #2099261) | Cod sursa (job #1372078)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int BFS(int src, vector<int> adjList[], int N, int &maxDist);
int main()
{
int N, a, b, i;
ifstream f("darb.in");
f >> N;
vector<int> adjList[N + 1];
for (i = 1; i < N; i++)
{
f >> a >> b;
adjList[a].push_back(b);
adjList[b].push_back(a);
}
f.close();
int diameter;
int chainHead = BFS(a, adjList, N, diameter);
BFS(chainHead, adjList, N, diameter);
ofstream g("darb.out");
g << diameter + 1;
g.close();
return 0;
}
int BFS(int src, vector<int> adjList[], int N, int &maxDist)
{
queue<int> q;
int d[N + 1], i;
bool visited[N + 1];
for (i = 1; i <= N; i++)
{
d[i] = 0;
visited[i] = false;
}
int x, lastNode = src;
visited[src] = true;
q.push(src);
while (!q.empty())
{
x = q.front(), q.pop();
for (i = 0; i < adjList[x].size(); i++)
if (!visited[adjList[x][i]])
{
visited[adjList[x][i]] = true;
d[adjList[x][i]] = d[x] + 1;
if (d[adjList[x][i]] > d[lastNode])
lastNode = adjList[x][i];
q.push(adjList[x][i]);
}
}
maxDist = d[lastNode];
return lastNode;
}