Cod sursa(job #3151129)

Utilizator KRISTY06Mateiu Ianis Cristian Vasile KRISTY06 Data 19 septembrie 2023 20:07:20
Problema Diametrul unui arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

const int MAX_LENGTH = 100000;

int maxLen;

vector<int> graph[MAX_LENGTH + 1];

void findLastNode(int nodesNr, int currentNode, int prevNode, int &lastNode) {
    for (vector<int>::iterator it = graph[currentNode].begin(); it < graph[currentNode].end(); ++it) {
        if (*it != prevNode) {
            findLastNode(nodesNr, *it, currentNode, lastNode);
            if (lastNode == 0) {
                lastNode = *it;
                return;
            }
        }
    }
}

void longestLen(int nodesNr, int currentNode, int prevNode, int len) {
    for (vector<int>::iterator it = graph[currentNode].begin(); it < graph[currentNode].end(); ++it) {
        if (*it != prevNode) {
            longestLen(nodesNr, *it, currentNode, len + 1);
            maxLen = max(len + 1, maxLen);
        }
    }
}

int main() {
    int nodesNr;
    fin >> nodesNr;
    for (int i = 1; i < nodesNr; ++i) {
        int start, end;
        fin >> start >> end;
        graph[start].push_back(end);
        graph[end].push_back(start);
    }
   // int lastNode = 0;
    for (int node = 1; node <= nodesNr; ++node) {
        if (graph[node].size() == 1) {
            longestLen(nodesNr, node, 0, 1);
        }
    }
   // findLastNode(nodesNr, 1, 0, lastNode);
   // cout << lastNode;
   // longestLen(nodesNr, lastNode, 0, 1);
    fout << maxLen;
    return 0;
}
/*
 11
 1 2
 1 3
 1 4
 2 5
 3 6
 4 7
 5 8
 5 9
 6 10
 10 11
 =>
 8
 
 6
 2 3
 6 2
 6 1
 6 5
 5 4
 =>
 5
 
 4
 1 4
 2 3
 3 4
 =>
 4
 
 4
 1 2
 1 3
 1 4
 =>
 3
 
 4
 1 2
 2 3
 3 4
 =>
 4
 
 2
 1 2
 =>
 2
 
 
 */