Cod sursa(job #2813142)

Utilizator izotova_dIzotova Daria izotova_d Data 5 decembrie 2021 20:32:29
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

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

class Graph
{
private:
	//number of nodes
	int n;
	//number of edges
	int e;
	bool oriented;
	//adj list for graph representation
	vector<vector<int>> adj_list;
public:
	
	Graph(int n, bool oriented)
	{
		this->n = n;
		this->e = 0;
		this->oriented = oriented;
		vector<int> empty;
		for (int i = 0; i < n; i++)
		{
			this->adj_list.push_back(empty);
		}
	}
	virtual ~Graph() {}

	void add_edge(int node1, int node2)
	{
		this->e++;
		this->adj_list[node1].push_back(node2);
		if (!oriented)
		{
			this->adj_list[node2].push_back(node1);
		}
	}

	pair<int,int> bfs_darb(int start_node)
	{
		deque<int> unvisited;
		vector<int> visited;
		vector<int> answer;
		vector<bool> unvisited2(this->n, false);
		vector<bool> visited2(this->n, false);

		for (int i = 0; i < this->n; i++)
		{
			answer.push_back(-1);
		}

		unvisited.push_back(start_node);
		unvisited2[start_node] = true;
		answer[start_node] = 1;
		int last_node = 0;

		while (!unvisited.empty())
		{
			for (unsigned int i = 0; i < this->adj_list[start_node].size(); i++)
			{
				int key;
				key = adj_list[start_node][i];

				if (!visited2[key] && !unvisited2[key])
				{
					unvisited.push_back(key);
					unvisited2[key] = true;
					answer[key] = answer[start_node] + 1;
					last_node = key;

				}

			}

			visited.push_back(start_node);
			visited2[start_node] = true;
			unvisited.pop_front();
			if (!unvisited.empty())
			{
				start_node = unvisited[0];
			}
		}
		int diameter = answer[last_node];
		return make_pair(last_node, diameter); 
	}

	void darb()
	{
		

		//starting node
		int SN = 1;

		int n1, n2;
		for (int i = 0; i < this->n; i++)
		{
			fin >> n1 >> n2;
			add_edge(n1 - 1, n2 - 1);
		}

		int last_el = bfs_darb(SN - 1).first;
		fout << bfs_darb(last_el).second;

	}
};



int main()
{
	int N;
	fin >> N;
	Graph g(N, false);
	g.darb();


	return 0;
}