Pagini recente » Cod sursa (job #2512102) | Cod sursa (job #2155762) | Cod sursa (job #2711582) | Cod sursa (job #3236934) | Cod sursa (job #2814153)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
class graf {
protected:
int noduri, muchii;
vector < vector < int >> adiacenta;
public:
// Constructor cu matrice de adiacenta data
graf(vector < vector < int >> listaAdiacenta, int noduri, int muchii): adiacenta(listaAdiacenta), noduri(noduri), muchii(muchii) {};
// Constructor fara matrice de adiacenta, se cu initalizeaza una goala
graf(int noduri, int muchii): adiacenta(noduri + 1), noduri(noduri), muchii(muchii) {};
vector < int > bfs(int);
int dfs();
};
class graf_neorientat : public graf{
private:
void dfsbiconex(int, vector < int >&, vector < int >&, stack < pair < int, int >>&, int&, vector < string >&);
void dfsCriticalConnections(int tata, vector < int >&, vector < int >&, int&, vector < vector < int >>&, vector < int >&);
vector < int > bfs(int, int&);
public:
graf_neorientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf(listaAdiacenta, noduri, muchii) {};
graf_neorientat(int noduri, int muchii): graf(noduri, muchii) {};
friend istream& operator>>(istream&, graf_neorientat&);
vector < string > biconex();
vector < vector < int >> criticalConnections();
int darb ();
};
istream& operator>>(istream& in, graf_neorientat& g) {
for (int i = 0; i < g.muchii; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
g.adiacenta[aux1].push_back(aux2);
g.adiacenta[aux2].push_back(aux1);
}
return in;
}
vector < int > graf_neorientat :: bfs(int start, int& finish) {
vector < int > rasp(noduri + 1, -1);
vector < int > vis(noduri + 1);
queue < int > q;
vis[start] = 1;
q.push(start);
rasp[start] = 0;
// Se baga pe rand in queue toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele
while (!q.empty()) {
int curr = q.front();
q.pop();
for (int i: adiacenta[curr]){
if (vis[i] == 0) {
vis[i] = 1;
q.push(i);
rasp[i] = rasp[curr] + 1;
finish = i;
}
}
}
return rasp;
}
int graf_neorientat :: darb(){
int m = 0, nod = 0, last = 0;
vector<int> v(bfs(1, last));
// for(int i = 1; i <= noduri; i++){
// if(v[i] > m){
// m = v[i];
// nod = i;
// }
// }
v = bfs(last, last);
return v[last]+1;
}
void darbDriver() {
// https://infoarena.ro/problema/darb
// Citire
ifstream in ("darb.in");
ofstream out("darb.out");
int n, m, a, b;
in >> n;
vector < vector < int >> listaAdiacenta(n + 1);
while(in >> a >> b){
listaAdiacenta[a].push_back(b);
listaAdiacenta[b].push_back(a);
}
graf_neorientat x(listaAdiacenta, n, m);
out << x.darb();
}
int main() {
// Se apeleaza functia corespunzatoare problemei
darbDriver();
return 0;
}