diameter.cpp

#include <iostream>
#include <queue>
#include <functional>

#define DEBUG

using GraphData = typename std::vector<int>;
using Graph = typename std::vector<std::vector<int>>;

void BFS(const GraphData& gdata, const Graph& graph) {
	int level = 0;
	std::vector<bool> visited(graph.size(), false);
	std::vector<int> levels(graph.size());
	std::queue<int> queue;

	queue.push(0);
	visited[0] = true;
	while(!queue.empty()) {
		int size = queue.size();
		while(size--) {
			int current = queue.front();
			queue.pop();
			std::cout << "Visited " << gdata[current] << '(' << current << ')' << '\n';
			levels[current] = level;
			for(int i : graph[current]) {				
				if(!visited[i])	{
					visited[i] = true;
					queue.push(i);
				}
			}
			std::cout << '\n';
		}
		level++;
		std::cout << '\n';		
	}
}

void DFS(Graph& graph) {
	int deepest_node = 0, deepest_depth = 0;
	std::vector<bool> visited(graph.size(), false);
	std::function<void(int, int)> dfs_util = [&](int node, int depth) {
		visited[node] = true;
		if(depth > deepest_depth) {
			deepest_depth = depth;
			deepest_node = node;
		}
		for(int i : graph[node])
			if(visited[i] == false)
				dfs_util(i, depth + 1);
	};
	dfs_util(0, 0);
	
	deepest_depth = 0;
	std::fill(visited.begin(), visited.end(), false);
	dfs_util(deepest_node, 0);
	
	std::cout << "Diameter: " << deepest_depth;
}

int main () {
	int n;
	std::cin >> n;

	std::vector<int> nodes(n);
	for(int i = 0; i < n; i++) {
		int num;
		std::cin >> num;
		nodes[i] = num;
	}

	#ifdef DEBUG
	std::cout << "Nodes: "; 
	for(auto i : nodes)
		std::cout << i << ' ';
	std::cout << '\n';
	#endif

	Graph graph(n);
	int edges;
	std::cin >> edges;
	
	for(int i= 0; i < edges; i++) {
		int from, to;			
		std::cin >> from >> to;
		graph[from].push_back(to);
		graph[to].push_back(from);
	}

	BFS(nodes, graph);
	DFS(graph);
 	return 0;
}