Cod sursa(job #2431873)

Utilizator rd211Dinucu David rd211 Data 21 iunie 2019 00:54:43
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ofstream fout("darb.out");
vector<int> graf[100005];
int n;
void addMuchie(int x,int y)
{
    graf[x].push_back(y);
    graf[y].push_back(x);
}
int viz[100005];
queue<int> cue;
int bfs(int x)
{
    cue.push(x);
    viz[x]=true;
    int cueFront;
    while(cue.size())
    {
        cueFront = cue.front();
        for(int i = 0;i<graf[cueFront].size();i++)
        {
            if(viz[graf[cueFront][i]]==0)
            {
                viz[graf[cueFront][i]]=1;
                cue.push(graf[cueFront][i]);
            }
        }
        cue.pop();
    }
    return cueFront;
}
int dfs(int x)
{
    int best=0;
    for(int i = 0;i<graf[x].size();i++)
    {
        if(viz[graf[x][i]]==0)
        {
            viz[graf[x][i]]=viz[x]+1;
            int temp1 = 1+dfs(graf[x][i]);
            if(temp1>best)
                best=temp1;
        }
    }
    return best;
}
void solve()
{
    int y = bfs(1);
    for(int i = 0;i<=n;i++)
        viz[i]=0;
    fout<<dfs(y)+1<<'\n';
}
class InParser {

private:
	FILE *fin;
	char *buff;
	int sp;
	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
};
int main()
{
    int x,y;
    InParser fin("darb.in");
    fin>>n;
    for(register int i = 1;i<n;i++)
        fin>>x>>y,addMuchie(x,y);
    solve();
    return 0;
}