Cod sursa(job #2058754)

Utilizator DawlauAndrei Blahovici Dawlau Data 6 noiembrie 2017 08:42:47
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<fstream>
#include<list>
#include<deque>
#include<bitset>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
const int NMAX=100005,INF=NMAX+5;
list<int>g[NMAX];
bitset<NMAX>vis;
int dist[NMAX],n,last_node,dmax=1;
void read_data(){
    int node1,node2;
    fin>>n;
    while(fin>>node1>>node2){
        g[node1].push_back(node2);
        g[node2].push_back(node1);
    }
}
void BFS1(){
    int node;
    list<int>::iterator it;
    deque<int>d;
    d.push_back(1);
    vis[1]=true;
    while(!d.empty()){
        node=d.front();
        d.pop_front();
        last_node=node;
        for(it=g[node].begin();it!=g[node].end();++it)
            if(!vis[*it]){
                vis[*it]=true;
                d.push_back(*it);
            }
    }
    vis.reset();
}
void BFS2(){
    int node;
    fill(dist+1,dist+1+n,INF);
    list<int>::iterator it;
    deque<int>d;
    d.push_back(last_node);
    vis[last_node]=true;
    dist[last_node]=1;
    while(!d.empty()){
        node=d.front();
        d.pop_front();
        for(it=g[node].begin();it!=g[node].end();++it)
            if(!vis[*it]){
                vis[*it]=true;
                d.push_back(*it);
                if(dist[*it]>dist[node]+1)
                    dist[*it]=dist[node]+1;
                if(dmax<dist[*it])
                    dmax=dist[*it];
            }
    }
}
int main(){
    read_data();
    BFS1();
    BFS2();
    fout<<dmax;
}