Pagini recente » Cod sursa (job #2325800) | Cod sursa (job #103716) | Cod sursa (job #2436055) | Cod sursa (job #218141) | Cod sursa (job #3151191)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
const int MAX_LENGTH = 100000;
int maxLen;
int lastNode;
vector<int> graph[MAX_LENGTH + 1];
void findLastNode(int nodesNr, int currentNode, int prevNode, int len) {
for (vector<int>::iterator it = graph[currentNode].begin(); it < graph[currentNode].end(); ++it) {
if (*it != prevNode) {
findLastNode(nodesNr, *it, currentNode, len + 1);
if (len + 1 > maxLen) {
maxLen = len + 1;
lastNode = *it;
}
}
}
}
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);
}
findLastNode(nodesNr, 1, 0, 1);
maxLen = 0;
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
*/