///SORA ANDREEA-IOANA, GRUPA 234
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
const int oo = 10000000;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
bool compara(int a, int b)
{
return (a > b);
}
class Graf
{
protected:
int nrN, nrM; ///Numar noduri, numar muchii
vector <vector<int>> listaAd; ///lista de adiacenta graf
public:
Graf(int, int, vector <vector<int>> &);
Graf(const Graf &graf);
~Graf();
int get_noduri() const;
int get_muchii() const;
vector <vector<int>> get_lista() const;
void afisare(ostream&);
friend ostream& operator<<(ostream& out, Graf &g); ///supraincarcare operator <<
///BFS
void BFS(ostream&, int);
///DFS
void DFS(ostream &);
///SortareTopologica
void sortareTopologica(ostream&, int []);
///HavelHakimi
int existaGrafHH(vector <int> &, int);
///ComponenteTareConexe
void ctc(vector <int>, stack <int>, vector <vector<int>>, vector <int>, ostream &);
///MuchiiCritice
void DfsMuchiiCritice(int, int, vector <int> &, vector <int> &, vector <int> &, vector <vector<int>> &, ostream &);
///PaduriDeMultimiDisjuncte
int Find(int, vector <int> &);
void Union(int, int, vector <int> &, vector <int> &);
protected:
///DFS
void DoDfs(int, vector <int> &);
///ComponenteTareConexe
void dfs1(int, vector <int> &, stack <int>&);
void dfs2(int, vector <int> &, vector <vector<int>>, vector <vector<int>> &, vector <int> &);
};
Graf :: Graf(int nrNoduri, int nrMuchii, vector <vector<int>> &lista)
{
nrN = nrNoduri;
nrM = nrMuchii;
listaAd = lista;
}
Graf :: Graf(const Graf & graf)
{
nrN = graf.nrN;
nrM = graf.nrM;
listaAd = graf.listaAd;
}
Graf :: ~Graf()
{
nrN = 0;
nrM = 0;
listaAd.clear();
}
int Graf :: get_noduri() const
{
return nrN;
}
int Graf :: get_muchii() const
{
return nrM;
}
vector <vector<int>> Graf :: get_lista() const
{
return listaAd;
}
void Graf :: afisare(ostream &out)
{
out << "Numar de noduri: " << nrN << "\n";
out << "Numar de muchii: " << nrM << "\n";
for (int i = 0; i < nrN; i++)
for (int j = 0; j < listaAd[i].size(); j++)
{
out << "Muchia " << i << " " << listaAd[i][j];
out << "\n";
}
}
ostream& operator<<(ostream& out, Graf &g)
{
g.afisare(out);
return out;
}
///BFS
void Graf :: BFS(ostream &out, int start)
{
int cost[nrN + 1], S;
for (int i = 1; i <= nrN; i++)
cost[i] = -1; ///initializam costurile cu -1
queue <int> coada;
coada.push(start); ///adaugam in coada nodul de start
cost[start] = 0; ///costul pentru nodul de start este 0
while (!coada.empty()) ///cat timp avem elemente in coada
{
S = coada.front();
for (int i = 0; i < listaAd[S].size(); i++) ///parcurgem vecinii nodului curent
{
int nod_curent = listaAd[S][i];
if (cost[nod_curent] == -1) ///daca e nevizitat
{
cost[nod_curent] = cost[S] + 1; ///actualizam costul
coada.push(nod_curent); ///adaugam in coada vecinul
}
}
coada.pop(); ///eliminam nodul curent din coada
}
for (int i = 1; i <= nrN; i++)
out << cost[i] << " "; ///afisam costurile pentru fiecare nod
}
///DFS
void Graf :: DoDfs(int nod, vector <int> &viz)
{
viz[nod] = 1; ///vizitam nodul curent
for (int i = 0; i < listaAd[nod].size(); i++) ///parcurgem vecinii nodului curent
{
int nod_curent = listaAd[nod][i];
if (viz[nod_curent] == 0) ///daca vecinul este nevizitat
DoDfs(nod_curent, viz);
}
}
void Graf :: DFS(ostream &out)
{
vector <int> viz(nrN + 1, 0); ///initializam vectorul viz
int nrCC = 0; ///numar componente conexe
for (int i = 1; i <= nrN; i++)
{
if (viz[i] == 0) ///daca nodul este nevizitat
{
DoDfs(i, viz);
nrCC ++;
}
}
out << nrCC;
}
///SortareTopologica
void Graf :: sortareTopologica(ostream &out, int grade[])
{
queue <int> coada;
vector <int> rez;
for (int i = 1; i <= nrN; i++)
if (grade[i] == 0)
coada.push(i); ///adaugam in coada nodurile cu gradul intern 0
while (!coada.empty())
{
int nod_curent = coada.front();
rez.push_back(nod_curent);
coada.pop();
for (int i = 0; i < listaAd[nod_curent].size(); i++) ///parcurgem vecinii
{
int vecin = listaAd[nod_curent][i];
grade[vecin]--; ///scadem 1 tuturor gradelor nodurilor adiacente
if (grade[vecin] == 0) ///daca gradul intern a devenit 0, il adaugam in coada
coada.push(vecin);
}
}
for (int i=0; i < rez.size(); i++)
out << rez[i] << " ";
}
///HavelHakimi
int Graf :: existaGrafHH(vector <int> &v, int n)
{
int ok = 1;
while (ok == 1)
{
sort(v.begin(), v.end(), compara); ///sortam descrescator gradele nodurilor
if (v[0] == 0) ///daca toate gradele sunt egale cu 0 - primul element 0 in ordine descrescatoare
break; ///exista graf
int nr = v[0]; ///extragem primul grad
v.erase(v.begin());
if (nr > v.size()) ///daca gradul este mai mare decat numarul de elemente ramase
{
ok = 0; ///nu exista graf
break;
}
for (int i = 0; i < nr; i++) ///parcurgem urmatoarele nr elemente
{
v[i] = v[i] - 1; ///scadem 1 din grad
if (v[i] < 0) ///daca gradul a devenit -1
{
ok = 0; ///nu exista graf
break;
}
}
}
if (ok == 1) return 1;
return 0;
}
///Ctc
void Graf :: dfs1(int nod, vector <int> &vizitat, stack <int> &stiva)
{
vizitat[nod] = 1;
for (int i = 0; i < listaAd[nod].size(); i++)
{
int nod_curent = listaAd[nod][i];
if (vizitat[nod_curent] == 0)
dfs1(nod_curent, vizitat, stiva);
}
stiva.push(nod); ///adaugam in stiva nodurile
}
void Graf :: dfs2(int nod, vector <int> &vizitatTr, vector <vector<int>> listaTr, vector <vector<int>> &rez, vector <int> &vector_aux)
{
vector_aux.push_back(nod); ///adaugam nodul la componenta curenta
vizitatTr[nod] = 1;
for (int i = 0; i < listaTr[nod].size(); i++)
{
int nod_curent = listaTr[nod][i];
if (vizitatTr[nod_curent] == 0)
dfs2(nod_curent, vizitatTr, listaTr, rez, vector_aux);
}
}
void Graf :: ctc(vector <int> vizitat, stack <int> stiva, vector <vector<int>> listaTr, vector <int> vizitatTr, ostream &out)
{
vector <vector<int>> rez(nrN + 1);
int nr = 0;
for (int i = 1; i <= nrN; i++)
if (vizitat[i] == 0)
dfs1(i, vizitat, stiva); ///primul dfs
while (!stiva.empty()) ///parcurgem stiva
{
int v = stiva.top();
stiva.pop();
if (vizitatTr[v] == 0) ///daca nodul curent din stiva e nevizitat
{
vector <int> vector_aux;
dfs2(v, vizitatTr, listaTr, rez, vector_aux); ///al doilea dfs
rez.push_back(vector_aux); ///adaugam la solutie componenta curenta
nr++; ///incrementam numarul de componente
}
}
out << "Numarul de componente tare conexe: " << nr << "\n";
//out << nr << "\n";
out << "Componentele: " << "\n";
for (int i = 0; i < rez.size(); i++)
{
if (rez[i].size() != 0)
{
for (int j = 0; j < rez[i].size(); j++)
out << rez[i][j] << " ";
out << "\n";
}
}
}
///MuchiiCritice
void Graf :: DfsMuchiiCritice(int nod, int tata, vector <int> &vizitat, vector <int> &nivel, vector <int> &nivelInt, vector <vector<int>> &listaAd,
ostream &out)
{
vizitat[nod] = 1;
nivel[nod] = nivel[tata] + 1; ///actualizam nivelul
nivelInt[nod] = nivel[nod]; ///actualizam nivelul de intoarcere
for (int i = 0; i < listaAd[nod].size(); i++)
{
int copil = listaAd[nod][i];
if (copil != tata)
{
if (vizitat[copil] == 1)
{
if (nivelInt[nod] > nivel[copil]) ///actualizam nivelul de intoarcere acolo unde gasim o muchie de intoarcere
nivelInt[nod] = nivel[copil];
}
else
{
DfsMuchiiCritice(copil, nod, vizitat, nivel, nivelInt, listaAd, out);
if (nivelInt[nod] > nivelInt[copil]) ///actualizam nivelul de intoarcere in cazul in care un copil are acest nivel mai mic
nivelInt[nod] = nivelInt[copil];
if (nivel[nod] < nivelInt[copil]) ///conditie muchii critice
out << nod << " " << copil << "\n";
}
}
}
}
///PaduriDeMultimiDisjuncte
int Graf :: Find(int nod, vector <int> &tata)
{
if (tata[nod] == nod)
return nod;
int rez = Find(tata[nod], tata);
tata[nod] = rez;
return rez;
}
void Graf :: Union(int nod1, int nod2, vector <int> &tata, vector <int> &rang)
{
int TataNod1 = Find(nod1, tata);
int TataNod2 = Find(nod2, tata);
if (TataNod1 == TataNod2)
return;
if (rang[TataNod1] < rang[TataNod2])
tata[TataNod1] = TataNod2;
else if (rang[TataNod1] > rang[TataNod2])
tata[TataNod2] = TataNod1;
else
{
tata[TataNod2] = TataNod1;
rang[TataNod1]++;
}
}
///---------------------Graf Ponderat - Muchii cu costuri-------------------------------
bool comparaCost (vector <int> v1, vector <int> v2)
{
return v1[2] < v2[2];
}
class GrafPonderat : public Graf
{
private:
vector <vector <pair<int, int>>> muchiiCuCost;
int find_tata(int, vector <int>);
void set_tata(int, int, vector <int> &);
public:
GrafPonderat(int, int, vector <vector <int>>, vector <vector<pair <int, int>>>);
vector <pair<int, int>> apmKruskal(ostream &, vector <int>, vector <vector <int>>);
void dijkstra(vector <int>&);
};
GrafPonderat :: GrafPonderat(int nrNoduri, int nrMuchii, vector <vector <int>> lista, vector <vector<pair<int, int>>> muchiiCost) : Graf(nrNoduri, nrMuchii, lista) ///apelam constructorul din baza
{
muchiiCuCost = muchiiCost;
}
int GrafPonderat :: find_tata(int nod, vector <int> tata)
{
while (nod != tata[nod])
nod = tata[nod];
return nod;
}
void GrafPonderat :: set_tata(int nod1, int nod2, vector <int> &tata)
{
tata[nod1] = tata[nod2];
}
vector <pair<int, int>> GrafPonderat :: apmKruskal(ostream &out, vector <int> tata, vector <vector <int>> muchiiCost)
{
vector <pair<int, int>> rez;
sort (muchiiCost.begin(), muchiiCost.end(), comparaCost); ///sortam muchiile crescator dupa cost
int cost_total = 0, nod1, nod2, tata1, tata2, nrMuchiiAPM = 0, index_muchie = 0;
while (nrMuchiiAPM < nrN - 1) ///parcurgem muchiile pana cand avem suficiente ca graful sa fie conex = (numar noduri - 1) muchii
{
nod1 = muchiiCost[index_muchie][0]; ///nod1 din muchia curenta
nod2 = muchiiCost[index_muchie][1]; ///nod2 din muchia curenta
///cautam radacina arborilor partiali din care fac parte nodurile
tata1 = find_tata(nod1, tata);
tata2 = find_tata(nod2, tata);
if (tata1 != tata2) ///am gasit muchie de adaugat in APM
{
if (tata1 < tata2)
set_tata(tata1, tata2, tata);
else
set_tata(tata2, tata1, tata);
rez.push_back(make_pair(nod1, nod2));
cost_total = cost_total + muchiiCost[index_muchie][2];
nrMuchiiAPM++;
}
index_muchie++;
}
out << cost_total << "\n";
out << nrMuchiiAPM << "\n";
return rez;
}
void GrafPonderat :: dijkstra(vector <int> &distante)
{
vector <bool> inCoada(nrN + 1, false);
priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair <int, int>>> coada;
distante[1] = 0;
coada.push({1, 0});
inCoada[1] = true;
while (!coada.empty())
{
int nodCurent = coada.top().first;
coada.pop();
inCoada[nodCurent] = false;
for (int i = 0; i < muchiiCuCost[nodCurent].size(); i++)
{
int vecin, cost_vecin;
vecin = muchiiCuCost[nodCurent][i].first;
cost_vecin = muchiiCuCost[nodCurent][i].second;
if (distante[nodCurent] + cost_vecin < distante[vecin])
{
distante[vecin] = distante[nodCurent] + cost_vecin;
if (inCoada[vecin] == 0)
{
coada.push({vecin, distante[vecin]});
inCoada[vecin] = true;
}
}
}
}
}
///-------------------------BFS------------------------------
void problemaBFS()
{
int n, s, st, dr, m;
cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
cout << "Introduceti numarul de noduri: ";
cin >> n;
cout << "Introduceti numarul de muchii: ";
cin >> m;
cout << "Introduceti nodul start: ";
cin >> s;
cout << "Introduceti muchiile: ";
//ifstream fin("bfs.in");
//ofstream fout("bfs.out");
//fin >> n >> m >> s;
vector <vector<int>> listaAd(n + 1);
for (int i = 1; i <= m; i++)
{
cin >> st >> dr;
//fin >> st >> dr;
listaAd[st].push_back(dr);
}
Graf g(n, m, listaAd);
g.BFS(cout, s);
//g.BFS(fout, s);
//fin.close();
//fout.close();
}
///-------------------------DFS--------------------------------
void problemaDFS()
{
int n, m, st, dr;
cout << "Numerotare noduri de la index 1! Graf neorientat!" << "\n";
cout << "Introduceti numarul de noduri: ";
cin >> n;
cout << "Introduceti numarul de muchii: ";
cin >> m;
cout << "Introduceti muchiile: ";
//ifstream fin("dfs.in");
//ofstream fout("dfs.out");
//fin >> n >> m;
vector <vector<int>> listaAd(n + 1);
for (int i = 1; i <= m; i++)
{
cin >> st >> dr;
//fin >> st >> dr;
listaAd[st].push_back(dr);
listaAd[dr].push_back(st);
}
Graf g(n, m, listaAd);
g.DFS(cout);
//g.DFS(fout);
//fin.close();
//fout.close();
}
///------------------Havel Hakimi-------------------------
void problemaHavelHakimi()
{
vector <int> v;
int n, el;
cout << "Introduceti numarul de elemente: ";
cin >> n;
cout << "Introduceti gradele: ";
for (int i = 0; i < n; i++)
{
cin >> el;
v.push_back(el);
}
vector <vector<int>> vgol(n+1,{0});
Graf g(0, 0, vgol);
int rez = g.existaGrafHH(v, n);
if (rez == 1)
cout << "Da, exista graf!";
else cout << "Nu, nu exista graf!";
}
///------------------Sortare Topologica------------------
void problemaSortareTopologica()
{
int n, m, st, dr, grade[50001] = {0};
cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
cout << "Introduceti numarul de noduri: ";
cin >> n;
cout << "Introduceti numarul de muchii: ";
cin >> m;
cout << "Introduceti muchiile: ";
//ifstream fin("sortaret.in");
//ofstream fout("sortaret.out");
//fin >> n >> m;
vector <vector<int>> listaAd (n + 1);
for (int i = 1; i <= m; i++)
{
cin >> st >> dr;
//fin >> st >> dr;
listaAd[st].push_back(dr);
grade[dr]++;
}
Graf g(n, m, listaAd);
g.sortareTopologica(cout, grade);
//g.sortareTopologica(fout, grade);
//fin.close();
//fout.close();
}
///---------------Componente Tare Conexe-------------------
void problemaComponenteTareConexe()
{
int n, m, st, dr;
cout << "Numerotare noduri de la index 1! Graf orientat!" << "\n";
cout << "Introduceti numarul de noduri: ";
cin >> n;
cout << "Introduceti numarul de muchii: ";
cin >> m;
cout << "Introduceti muchiile: ";
//ifstream fin("ctc.in");
//ofstream fout("ctc.out");
//fin >> n >> m;
vector <vector<int>> listaTr(n + 1);
vector <vector<int>> listaAd(n + 1);
vector <int> vizitat(n + 1, 0);
vector <int> vizitatTr(n + 1, 0);
stack <int> stiva;
for (int i = 1; i <= m; i++)
{
cin >> st >> dr;
//fin >> st >> dr;
listaAd[st].push_back(dr);
listaTr[dr].push_back(st);
}
Graf g(n, m, listaAd);
g.ctc(vizitat, stiva, listaTr, vizitatTr, cout);
//g.ctc(fout);
//fin.close();
//fout.close();
}
///------------------Muchii Critice---------------------
void problemaCriticalConnectionsLeetCode()
{
int n, m, st, dr;
cout << "Numerotare noduri de la index 0! Graf neorientat!" << "\n";
cout << "Introduceti numarul de noduri: ";
cin >> n;
cout << "Introduceti numarul de muchii: ";
cin >> m;
cout << "Introduceti muchiile: ";
vector <vector<int>> listaAd(n + 1);
vector <int> vizitat(n + 1, 0);
vector <int> nivel(n + 1, 0);
vector <int>nivelInt(n + 1, 0);
for (int i = 1; i <= m; i++)
{
cin >> st >> dr;
listaAd[st].push_back(dr);
listaAd[dr].push_back(st);
}
Graf g(n, m, listaAd);
cout << "Muchii critice: ";
g.DfsMuchiiCritice(0, 0, vizitat, nivel, nivelInt, listaAd, cout);
}
///---------------Paduri De Multimi Disjuncte------------------
void problemaPaduriDeMultimiDisjuncte()
{
// ifstream fin("disjoint.in");
// ofstream fout("disjoint.out");
int n, m, st, dr, operatie;
//fin >> n >> m;
cout << "Introduceti numarul de multimi: ";
cin >> n;
cout << "Introduceti numarul de operatii efectuate: ";
cin >> m;
cout << "Operatie 1: Reuneste multimile unde se afla elementul x, respectiv y" << "\n";
cout << "Operatie 2: Afiseaza 'DA' daca cele doua elemente se afla in aceeasi multime, 'NU' in caz contrar" << "\n";
cout << "Introduceti valorile de forma: operatie - elementul x - elementul y: ";
vector <vector<int>> vgol(n + 1,{0});
vector <int> tata(n + 1);
vector <int> rang(n + 1, 0);
Graf g(n, m, vgol);
for (int i = 1; i <= n; i++)
tata[i] = i;
for (int i = 1; i <= m; i++)
{
cin >> operatie >> st >> dr;
if (operatie == 1)
{
g.Union(st, dr, tata, rang);
}
else if (g.Find(st, tata) == g.Find(dr, tata))
cout << "DA" << "\n";
else cout << "NU" << "\n";
}
// fin.close();
// fout.close();
}
///---------------------APM Kruskal-------------------------
void problemaAPMKruskal()
{
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, st, dr, cost;
//cout << "Introduceti numarul de noduri: ";
//cin >> n;
//cout << "Introduceti numarul de muchii: ";
//cin >> m;
//cout << "Introduceti muchiile si costul acestora: " << "\n";
fin >> n >> m;
vector <vector <int>> lista(n + 1, {0});
vector <vector<pair <int, int>>> muchiiCuCost(n + 1, {{0,0}});
vector <vector <int>> muchiiCost;
for (int i = 1; i <= m; i++)
{
// cin >> st >> dr >> cost;
fin >> st >> dr >> cost;
muchiiCost.push_back({st, dr, cost});
}
GrafPonderat g(n, m, lista, muchiiCuCost);
vector <int> tata(n + 1);
for (int i = 1; i <= n; i++)
tata[i] = i;
vector <pair<int, int>> rezultat = g.apmKruskal(fout, tata, muchiiCost);
for (int i = 0; i < rezultat.size(); i++)
fout << rezultat[i].first << " " << rezultat[i].second << "\n";
fin.close();
fout.close();
}
///----------------------------Dijkstra----------------------------------
void problemaDijkstra()
{
int n, m, st, dr, cost;
fin >> n >> m;
vector <vector <int>> lista;
vector <vector<pair <int, int>>> muchiiCuCost(n + 1);
for (int i = 1; i <= m; i++)
{
fin >> st >> dr >> cost;
muchiiCuCost[st].push_back(make_pair(dr, cost));
}
GrafPonderat g(n, m, lista, muchiiCuCost);
vector <int> distante(n + 1, oo);
g.dijkstra(distante);
for (int i = 2; i <= n; i++)
if (distante[i] == oo)
fout << 0 << " ";
else
fout << distante[i] << " ";
fin.close();
fout.close();
}
int main()
{
/*cout << "---Sora Andreea-Ioana/grupa 234/Tema 1 - Algoritmi Fundamentali---" << "\n";
cout << "Probleme: " << "\n";
cout << "1. BFS - drumuri minime de la un nod start la toate celelalte" << "\n";
cout << "2. DFS - Numarul de componente conexe" << "\n";
cout << "3. Sortare Topologica" << "\n";
cout << "4. Havel Hakimi" << "\n";
cout << "5. Componente Tare Conexe" << "\n";
cout << "6. Muchii Critice - LeetCode" << "\n";
cout << "7. Paduri De Multimi Disjuncte" << "\n";
cout << "8. Arbore Partial de Cost Minim - Kruskal" << "\n";
cout << "9. Dijkstra - distante minime din nodul de start 1" << "\n";
cout << "Introduceti numarul problemei pe care doriti sa o rulati: ";
int numar;
cin >> numar;
cout << "\n";
if (numar < 1 || numar >= 10)
cout << "Numar invalid!";
else if (numar == 1) problemaBFS();
else if (numar == 2) problemaDFS();
else if (numar == 3) problemaSortareTopologica();
else if (numar == 4) problemaHavelHakimi();
///HavelHakimi
///(2,2,2,2) -> (1,1,2) -> (2,1,1) -> (0,0)
/// nod ------- nod
/// | |
/// | |
/// nod-------- nod
/// (3,2,1,1,0) -> (1,0,0,0) -> (-1,0,0)
else if (numar == 5) problemaComponenteTareConexe();
else if (numar == 6) problemaCriticalConnectionsLeetCode();
else if (numar == 7) problemaPaduriDeMultimiDisjuncte();
else if (numar == 8) problemaAPMKruskal();
else if (numar == 9) problemaDijkstra();*/
problemaDijkstra();
return 0;
}