Cod sursa(job #1929201)

Utilizator Kln1000Ciobanu Bogdan Kln1000 Data 17 martie 2017 11:52:44
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.68 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

class parser{
    public:
        parser() {}
        parser(const char *file_name){
            input_file.open(file_name,ios::in | ios::binary);
            input_file.sync_with_stdio(false);
            index&=0;
            input_file.read(buffer,SIZE);}
        inline parser &operator >>(int &n){
            for (;buffer[index]<'0' or buffer[index]>'9';inc());
            n&=0;
            for (;'0'<=buffer[index] and buffer[index]<='9';inc())
                n=(n<<3)+(n<<1)+buffer[index]-'0';
            return *this;}
            ~parser(){
            input_file.close();}
    private:
        fstream input_file;
        static const int SIZE=0x400000;
        char buffer[SIZE];
        int index;
        inline void inc(){
            if(++index==SIZE)
                index&=0,input_file.read(buffer,SIZE);}
};

parser f ("darb.in");
ofstream t ("darb.out");

vector <int> v[100010];
int n,last,dist[100010];

void dfs(int nod){
    bitset <100010> vaz;
    vector <int> stack;
    stack.push_back(nod);
    vaz[nod]=true;
    dist[nod]=1;
    while (!stack.empty()){
        int current=stack.back();
        if (dist[current]>dist[last]) last=current;
        stack.pop_back();
        for (auto i:v[current])
            if (!vaz[i])
                vaz[i]=true,
                stack.push_back(i),
                dist[i]=1+dist[current];
    }
}

int main()
{
    f>>n;
    for (int x,y,i=1;i<n;++i)
        f>>x>>y,
        v[x].push_back(y),
        v[y].push_back(x);
    dfs(1);
    dfs(last);
    t<<dist[last];
    return 0;
}