Pagini recente » Cod sursa (job #1005268) | Cod sursa (job #1683756) | Cod sursa (job #1126849) | Cod sursa (job #1401459) | Cod sursa (job #2182633)
#include <bits/stdc++.h>
#define NMax 100005
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n, ap[NMax], T[NMax], nr;
vector <int> G[NMax];
queue <int> q;
pair <int, int> ramura[NMax];
void BFS(int start){
q.push(start);
T[start] = start;
ap[start] = 1;
while(!q.empty())
{
int nod = q.front();
q.pop();
for(int i = 0; i < G[nod].size(); i++)
{
int vecin = G[nod][i];
if(!ap[vecin])
{
ap[vecin] = 1;
q.push(vecin);
T[vecin] = nod;
}
}
}
}
int nr_root(int i){
while(T[T[i]] != T[i])
{
i = T[i];
nr++;
}
return i;
}
int main(){
fin >> n;
while(true)
{
if(fin.eof()) break;
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
BFS(1);
int Max = 0;
for(int i = 1; i <= n; i++)
{
nr = 1;
int root = nr_root(i);
ramura[i].first = nr;
ramura[i].second = root;
}
int t = 1;
for(int i = 2; i < n; i++)
if(ramura[i].second != ramura[i+1].second) t = 0;
sort(ramura+1, ramura+n+1);
if(t == 0)
{
int dist1 = ramura[n].first;
int ramura1 = ramura[n].second;
int nr_total = 0;
for(int i = n-1; i >= 1; i--)
{
int dist2 = ramura[i].first;
int ramura2 = ramura[i].second;
if(ramura1 != ramura2)
{
nr_total = dist1 + dist2;
break;
}
}
fout << nr_total + 1;
}
if(t == 1)
fout << ramura[n].first + 1;
}