Cod sursa(job #2610351)

Utilizator mzzmaraMara-Ioana Nicolae mzzmara Data 4 mai 2020 19:15:40
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h> 

using namespace std;

const int kNmax = 100005;

class Task {
 public:
	void solve() {
		read_input();
        get_result();
		print_output();
	}

 private:
	int n;
	vector<int> adj[kNmax];
	int maxSize;
	int bound;

	void read_input() {
		ifstream fin("darb.in");

		fin >> n;
	
		for (int i = 1, x, y; i < n; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		fin.close();
	}


	void get_result() {
		maxSize = INT_MIN;
		bound = 0;

		std::vector<bool> visited(n + 1, false); 
        dfsHelper(1, visited, 1);

		visited = std::vector<bool>(n + 1, false); 
		dfsHelper(bound, visited, 1);
    }

    void dfsHelper(int node, std::vector<bool> &visited, int size) { 
        visited[node] = true;
		size++;
        for (auto& adj : adj[node]) { 
            if (!visited[adj]) {

				if (size >= maxSize) {
					maxSize = size;
					bound = adj;
				}

                dfsHelper(adj, visited, size);
            }
		}
    }

	void print_output() {
		ofstream fout("darb.out");
		fout << maxSize << "\n";
		fout.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}