Pagini recente » Istoria paginii runda/simoji/clasament | Cod sursa (job #1392177) | Cod sursa (job #2252825) | Cod sursa (job #2537287) | Cod sursa (job #2813536)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>
#include <tuple>
std::ifstream f("darb.in");
std::ofstream g("darb.out");
using namespace std;
class graf{
private:
int n,m,distmax,nod;
vector <int> vizitate;
vector <int> distanta;
vector <vector <int> > muchii;
public:
graf(int n);
void citire_muchii(int n);
void DFS_distanta(int s, int dist);
int gasire_dist_max();
int gasire_nod();
};
graf::graf(int n)
{
this->n=n;
}
void graf::citire_muchii(int n)
{
int start_edge, end_edge;
f>>n;
for(int i=1;i<n;i++)
{f>>start_edge>>end_edge;
muchii[start_edge].push_back(end_edge);}
}
void graf::DFS_distanta(int s, int dist)
{ distanta[s]=dist;
vizitate[s] = 1;
for (int i : muchii[s])
{
if (vizitate[i] == 0)
{
DFS_distanta(i, dist+1);
}
}
}
int graf:: gasire_dist_max(){
for(int i=0;i<=n;i++)
{
if (distanta[i]>distmax)
{
distmax=distanta[i];
nod=i;
}
}
return distmax;}
int graf:: gasire_nod(){
for(int i=0;i<=n;i++)
{
if (distanta[i]>distmax)
{
nod=i;
}
}
return nod;}
int main()
{
int n,m,distmax=0,nodcudistmax=0;
graf gr(n);
vector <int> vizitate;
vector <int> distanta;
distanta.resize(n+1);
vizitate.resize(n+1);
gr.DFS_distanta(1,0);
int nod=gr.gasire_nod();
for(int i=0;i<=n;i++) //ca sa putem aplica dfs din nou fara probleme din nodul final
{
distanta[i]=0;
vizitate[i] = 0;
}
gr.DFS_distanta(nod, 0);
int maxim=gr.gasire_dist_max();
g << "diametrul este:" << maxim; //????????/ eroare
f.close();
g.close();
return 0;
}