Pagini recente » Cod sursa (job #1954421) | Cod sursa (job #1589778) | Cod sursa (job #906956) | Cod sursa (job #652609) | Cod sursa (job #2813139)
#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;
}