Cod sursa(job #1565742)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 11 ianuarie 2016 11:55:29
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int NMAX=100005;
vector<int> g[NMAX];
queue<int> q;
int vis[NMAX], counter[NMAX];
int diameter, last;
void bfs(int u)
{
    memset(vis, 0, sizeof(vis));
    memset(counter, 0, sizeof(counter));
    q.push(u);
    vis[u]=1;
    counter[u]=1;
    while(!q.empty())
    {
        int node=q.front();
        for(int i=0; i<g[node].size(); i++)
        {
            int v=g[node][i];
            if(!vis[v])
            {
                q.push(v);
                counter[v]=counter[node]+1;
                vis[v]=1;
                diameter=counter[v];
                last=v;
            }
        }
        q.pop();
    }
}
int main()
{
    ifstream in("darb.in");
    ofstream out("darb.out");
    int n, i, u, v;
    in>>n;
    for(i=1; i<n; i++)
    {
        in>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs(1);
    bfs(last);
    out<<diameter<<'\n';
    return 0;
}