Pagini recente » Cod sursa (job #6812) | Cod sursa (job #1471997) | Cod sursa (job #150765) | Cod sursa (job #3195749) | Cod sursa (job #3151129)
#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
*/