Cod sursa(job #1958064)

Utilizator cazonirobertCazoni robert cazonirobert Data 7 aprilie 2017 23:14:39
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <stack>
#include <list>	
#include <algorithm>
#include <limits.h>

using namespace std;

//longest chain in a tree

ifstream f("darb.in");
ofstream g("darb.out");

int LC[100001];
int LB[100001];
int m, n = 0;  	// m - nr of egdes
				// n - nr of nodes, INDEXED from 1 

vector<int> tree[100001];

int longestBranch(int root){
	if(LB[root] != 0){
		return LB[root]; 
	}

	LB[root] = 1;
	vector<int> connectedNodes = tree[root];
	if(connectedNodes.size() == 0){
		return 1;
	}
	
	int maxx = INT_MIN;
	for(int node: connectedNodes){
		maxx = max(maxx, longestBranch(node));
	}
	LB[root] = maxx + 1;

	return LB[root];
}

int longestChain(int root){
	if(LC[root] != 0){
		return LC[root];
	}
	LC[root] = 1;
	vector<int> connectedNodes = tree[root];
	if(connectedNodes.size() == 0){
		return 1;
	}

	int maxLC = INT_MIN;
	int maxLB = INT_MIN;

	for(int node: connectedNodes){
		maxLC = max(maxLC, longestChain(node));
	}
	if(connectedNodes.size() == 1){
		maxLB = 1 + longestBranch(connectedNodes.back());
		LC[root] = max(maxLC, 1 + maxLB);
	} else {
		int maxLB1 = INT_MIN, maxLB2 = INT_MIN;
		for(int node: connectedNodes){
			if (longestBranch(node) > maxLB1){
				maxLB2 = maxLB1;	
				maxLB1  = longestBranch(node);
			} else if(longestBranch(node) > maxLB2){
				maxLB2 = longestBranch(node);
			}
		}
		maxLB = maxLB1 + maxLB2;
	}
	LC[root] = max(maxLC, 1 + maxLB);

	return LC[root];
}


int main(){
	f >> n;
	m = n - 1;
	for(int i = 0; i < m; i++){
		int from, to;
		f >> from >> to;
		tree[from].push_back(to);
	}
	/// print check
	// for(int i = 1; i <= n; i++){
	// 	vector<int> inter = tree[i];
	// 	cout << i << ": ";
	// 	for(int j = 0; j < inter.size(); j++){
	// 		cout << inter[j] << " ";
	// 	}
	// 	cout << endl;
	// }
	//
	g << longestChain(1) << endl;

	return 0;
}