Cod sursa(job #2610508)

Utilizator RaduNichitaRadu Nichita RaduNichita Data 4 mai 2020 22:42:04
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
	
#include <vector>
	
#include <fstream>
	
using namespace std;
	
 
	
 
	
 
	
#define NMAX 100005
	
 
	
class Task {
	
    std::vector<int> matrix[NMAX];
    std::vector<bool> visited;

	
    int N;
    int M;
    int length, current_size;
    int start_second;
	
 
	
    void read_input() {
        std::ifstream in("darb.in");
        in >> N;
        visited = std::vector<bool> (N + 1, false);
	
	
        for (int i = 0; i < N - 1; i++) {
            int x;
            int y;
            in >> x;
            in >> y;
            matrix[x].push_back(y);
            matrix[y].push_back(x);
        }
	
        in.close();
	
    }
	
 
	
    void show_matrix() {
	
        for (int i = 0; i < N; i++) {
	
            std::cout<<i<<":";
	
            for (int j = 0; j < matrix[i].size(); j++) {
	
                std::cout<<matrix[i][j]<<" ";
	
            }
	
            std::cout<<"\n";
	
        }
	
    }
	
 
	
    void DFS_UTIL(int node, int csize) {
        visited[node] = true;
        csize++;
        for (int i = 0; i < matrix[node].size(); i++) {
            if (visited[matrix[node][i]] == false) {
                if (length < csize) {
                    length = csize;
                    start_second = matrix[node][i];
                }

                DFS_UTIL(matrix[node][i], csize);
	
            }
	
        }
	
    } 
	
 
	
    int DFS() {
        length = INT32_MIN;
        DFS_UTIL(1,current_size);
        visited = std::vector<bool> (N + 1);
        DFS_UTIL(start_second, current_size);

    }
	
 
	
    void print() {
	
        std::ofstream out("darb.out");   
        out<<length + 1<<"\n";
	
        out.close();
	
        return;
	
    }
	
 
	
 public:
	
    void solve() {
	
        read_input();
        DFS();
        print();
	
    }
	
 
	
};
	
 
	
int main() {
	
 
	
    Task* task = new Task();
	
    task->solve();
	
    delete(task);
	
 
	
    return 0;
	
}