#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
// Clasa pentru graf
class graf {
protected:
// Numarul de noduri si numarul de muchii al grafului
int noduri, muchii;
// Matricea de adiacenta a grafului
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) {};
// Parcurgerea in latime a unui graf. Pornind de la un nod, se parcurg toti vecinii lui si se adauga intr-un queue. Se noteaza timpul la care se ajunge la fiecare.
vector < int > bfs(const int);
// Parcurgea in inaltime a unui graf. Pornind de la un nod, se parcurg toti vecinii lui si se adauga intr-un stack. Se noteaza timpul la care se ajunge la fiecare.
vector < int > dfs(const int);
// Se va face dfs atat timp cat exista un nod care nu a fost accesat de dfs-ul anterior.
int componenteConexe();
};
// Clasa pentru graf neorientat
class grafNeorientat : public graf {
// Functii auxiliare.
void dfsBiconex(int, vector < int >&, vector < int >&, stack < pair < int, int >>&, int&, vector < string >&);
void dfsCriticalConnections(int, vector < int >&, vector < int >&, int&, vector < vector < int >>&, vector < int >&);
int bfsDarb(const int, int&);
public:
// Constructor cu matrice de adiacenta data
grafNeorientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii) : graf(listaAdiacenta, noduri, muchii) {};
// Constructor fara matrice de adiacenta, se cu initalizeaza una goala
grafNeorientat(int noduri, int muchii) : graf(noduri, muchii) {};
// Functie care returneaza componentele biconexe ale unui graf neorientat
vector < string > biconex();
// Functie care returneaza muchiile critice ale unui graf neorientat
vector < vector < int >> criticalConnections();
// Functie care returneaza diametrul unui arbore
int darb();
// Functie care verifica daca un graf neorientat poate fi eulerian
bool isEuler();
// Functie care returneaza ciclul euler al unui graf eulerian
vector<int> euler();
};
// Clasa pentru graf orientat
class grafOrientat : public graf {
// Functii auxiliare
void dfsCtc(int, vector < int >&, vector < int >&, stack < int >&, int&, vector < string >&, unordered_set < int >&);
void dfsSortaret(int, vector < int >&, vector < int >&);
public:
// Constructor cu matrice de adiacenta data
grafOrientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii) : graf(listaAdiacenta, noduri, muchii) {};
// Constructor fara matrice de adiacenta, se cu initalizeaza una goala
grafOrientat(int noduri, int muchii) : graf(noduri, muchii) {};
// Functie care returneaza componentele tare conexe ale unui graf orientat
vector < string > ctc();
// Functie care returneaza o sortare topologica a unui graf orientat
vector < int > sortaret();
};
// Clasa pentru graf neorientat ponderat
class grafNeorientatPonderat : public grafNeorientat {
// Matrice de adianceta care contine si costurile
vector< vector< pair< int, int >>> adiacentaPonderata;
public:
// Constructor cu matrice de adiacenta data
grafNeorientatPonderat(vector < vector < pair<int, int> >> listaAdiacenta, int noduri, int muchii) : adiacentaPonderata(listaAdiacenta), grafNeorientat(noduri, muchii) {};
// Constructor fara matrice de adiacenta, se cu initalizeaza una goala
grafNeorientatPonderat(int noduri, int muchii) : adiacentaPonderata(noduri + 1), grafNeorientat(noduri, muchii) {};
// Functie care creeaza un graf partial de cost minim pornind de la un graf ponderat
vector< vector< int >> apm(vector< vector< int >>&, ostream&);
// Functie care returneaza drumul minim de la nodul 1 la fiecare nod din graf neorientat. Merge si pe costuri negative
unordered_map<int, int> bellmanFord();
};
// Clasa pentru graf orientat ponderat
class grafOrientatPonderat : public grafOrientat {
// Matrice de adianceta care contine si costurile
vector< vector< pair< int, int >>> adiacentaPonderata;
public:
// Constructor cu matrice de adiacenta data
grafOrientatPonderat(vector< vector< pair< int, int >>> listaAdiacenta, int noduri, int muchii) : adiacentaPonderata(listaAdiacenta), grafOrientat(noduri, muchii) {};
// Constructor cu matrice de adiacenta fara costuri data
grafOrientatPonderat(vector<vector<int>> listaAdiacenta, int noduri, int muchii) : grafOrientat(listaAdiacenta, noduri, muchii) {};
// Constructor fara matrice de adiacenta, se cu initalizeaza una goala
grafOrientatPonderat(int noduri, int muchii) : adiacentaPonderata(noduri + 1), grafOrientat(noduri, muchii) {};
// Functie care returneaza drumul minim de la nodul 1 la fiecare nod din graf orientat
unordered_map<int, int> dijkstra();
// Functie care returneaza pornind de la matricea de adiacenta cu costuri cel mai scurt drum de la fiecare nod la fiecare nod
vector<vector<int>> royFloyd(vector<vector<int>>);
// Functie care returneaza ciclul hamiltonian de cost minim al unui graf hamiltonian
int hamilton(vector<vector<int>>);
};
// Clasa pentru retea
class retea : public grafOrientat {
// Matrice de adianceta care contine si costurile
vector< vector< pair< int, int >>> adiacentaPonderata;
vector<vector<int>> cost;
// Functie auxiliara
bool auxBfs(const int start, vector<int>& parinti, vector<vector<int>> matrice, vector<vector<int>> cost);
public:
// Constructor cu matrice de adiacenta data
retea(vector< vector< pair< int, int >>> listaAdiacenta, int noduri, int muchii) : adiacentaPonderata(listaAdiacenta), grafOrientat(noduri, muchii) {};
// Constructor fara matrice de adiacenta, se cu initalizeaza una goala
retea(int noduri, int muchii) : adiacentaPonderata(noduri + 1), grafOrientat(noduri, muchii) {};
// Functie care primeste o retea si returneaza fluxul maxim care poate fi transmis de la sursa la desinatie prin retea
int maxflow();
};
// Clasa pentru graf bipartit
class grafBipartit : public grafNeorientat {
// Numarul de noduri din dreapta, respectiv stanga grafului bipartit
int stanga, dreapta;
// Functii auxiliare
bool bfsCuplaj(vector<int>&, vector<int>&, vector<int>&);
bool dfsCuplaj(int, vector<int>&, vector<int>&, vector<int>&);
public:
// Constructor fara matrice de adiacenta, se cu initalizeaza una goala
grafBipartit(vector<vector<int>> listaAdiacenta, int stanga, int dreapta, int muchii) : stanga(stanga), dreapta(dreapta), grafNeorientat(listaAdiacenta, stanga + dreapta, muchii) {};
// Algoritmul Hopcroft-Karp pentru a gasi cuplajul maxim intr-un graf bipartit
vector<pair<int, int>> cuplaj();
};
// Functii pentru clasa graf
// Parcurgerea in latime a unui graf. Pornind de la un nod, se parcurg toti vecinii lui si se adauga intr-un queue. Se noteaza timpul la care se ajunge la fiecare.
vector < int > graf::bfs(const int start) {
vector < int > rasp(noduri + 1, -1);
vector < int > vis(noduri + 1);
queue < int > q;
// Se incepe de la nodul start
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 nod : adiacenta[curr])
if (vis[nod] == 0) {
vis[nod] = 1;
q.push(nod);
rasp[nod] = rasp[curr] + 1;
};
}
return rasp;
}
// Parcurgea in inaltime a unui graf. Pornind de la un nod, se parcurg toti vecinii lui si se adauga intr-un stack. Se noteaza timpul la care se ajunge la fiecare.
vector < int > graf::dfs(const int start) {
vector < int > rasp(noduri + 1, -1);
vector < int > vis(noduri + 1);
stack < int > s;
// Se incepe de la nodul start
vis[start] = 1;
s.push(start);
rasp[start] = 0;
// Se baga pe rand in stack toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele. Se simuleaza call stack-ul de la recursivitate de dfs
while (!s.empty()) {
int curr = s.top();
s.pop();
for (int nod : adiacenta[curr]) {
if (vis[nod] == 0) {
vis[nod] = 1;
s.push(nod);
rasp[nod] = rasp[curr] + 1;
}
}
}
return rasp;
}
// Se va face dfs atat timp cat exista un nod care nu a fost accesat de dfs-ul anterior.
int graf::componenteConexe() {
vector < int > vis(noduri + 1);
int res = 0;
stack < int > s;
// Se baga pe rand in stack toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele. Se simuleaza call stack-ul de la recursivitate de dfs
for (int i = 1; i <= noduri; i++) {
if (vis[i] == 0) {
res++;
vis[i] = 1;
s.push(i);
while (!s.empty()) {
int curr = s.top();
s.pop();
for (int i = adiacenta[curr].size() - 1; i >= 0; i--) {
int nod = adiacenta[curr][i];
if (vis[nod] == 0) {
vis[nod] = 1;
s.push(nod);
}
}
}
}
}
return res;
}
// Functii pentru clasa graf neorientat
// Determina componentele biconexe ale unui graf neorientat, si le pune in vectorul 'rasp'.
void grafNeorientat::dfsBiconex(int tata, vector < int >& timp, vector < int >& rev, stack < pair < int, int >>& s, int& timpCurent, vector < string >& rasp) {
// Tarjan modificat
timpCurent++;
timp[tata] = timpCurent;
rev[tata] = timpCurent;
int fiuRadacina = 0;
// Se tin minte timpii de intoarcere respectiv timpul de intalnire al fiecarui nod in arborele de dfs call
for (int fiu : adiacenta[tata]) {
if (timp[fiu] == -1) {
// Se retine cati fii are fiecare nod in arborele de call dfs
fiuRadacina++;
// Se parcurge prin dfs fiecare nod, si cand se gaseste un nod nevizitat se adauga muchia intr-un stack
s.push(make_pair(tata, fiu));
dfsBiconex(fiu, timp, rev, s, timpCurent, rasp);
// Timpul de revenire al unei muchii este minimul dintre timpul de revenire curent si timpul de revenire al fiului,
// pt ca daca fiul are timp de revenire mai mic si tata il va putea accesa
rev[tata] = min(rev[tata], rev[fiu]);
if ((timp[tata] != 1 && rev[fiu] >= timp[tata]) || (timp[tata] == 1 && fiuRadacina > 1)) {
// Se verifica daca un nod e critic, si sunt 2 cazuri. Primul e cand nodul nu e chiar nodul de incepere al dfs, iar timpul de revenire al fiului este mai mare ca tatal.
// Practic cand nu suntem intr-un ciclu. Al doilea caz este cel discutat la laborator, cand nodul este chiar radacina arborelui, daca are 2 fii atunci e clar nod critic
pair < int, int > stop = make_pair(tata, fiu);
unordered_set < int > aux;
string str = "";
// Se face afisare cu string
aux.insert(stop.first);
aux.insert(stop.second);
str += to_string(stop.first);
str += " ";
str += to_string(stop.second);
str += " ";
// Se parcurge stackul de muchii pana cand dam de muchia care leaga fiul de tata.
// Se face asta pt ca mai intai se va adauga o muchie intre fiu si tata in stack, apoi se va face dfs
// si se vor detecta componentele biconexe ale descendentilor si se vor adauga in stack muchiile descendentilor, iar cad se va iesi din dfs-ul descendentilor unui nod tata
// ce vor ramane in stack vor fi chiar muchiile corespunzatoare componentei biconexe, pana la muchia care leaga tatal de fiu
while (s.top() != stop) {
int nodcur = s.top().first;
if (aux.find(nodcur) == aux.end()) {
str += to_string(nodcur);
str += " ";
aux.insert(s.top().first);
}
s.pop();
}
str += '\n';
rasp.push_back(str);
s.pop();
}
}
else {
// Daca nodul e deja vizitat, atunci am detectat o muchie de intoarcere,
// si timpul de revenire al tatalui devine minimul dintre timpul actual de revenire (ca poate fi mai mic, cu o alta muchie gasita deja)
// si timpul de gasire al fiului
rev[tata] = min(rev[tata], timp[fiu]);
// Verificam sa nu fie o muchie care sa duca in fata (in arbore) de fapt, pt ca deja a fost analizata mai devreme in dfs
if (timp[fiu] < timp[tata]) {
s.push(make_pair(tata, fiu));
}
}
}
}
// Functie care returneaza componentele biconexe ale unui graf neorientat
vector < string > grafNeorientat::biconex() {
vector < int > timp(noduri + 1, -1), rev(noduri + 1);
stack < pair < int, int >> s;
vector < string > rasp;
int timpo = 0;
// Se porneste dfs-ul din toate componentele conexe, si apoi se adauga la raspuns si ce a mai ramas in stack, pt ca si ce ramane va forma o componenta biconexa
for (int i = 0; i < noduri; i++) {
if (timp[i] == -1) {
dfsBiconex(i, timp, rev, s, timpo, rasp);
}
if (!s.empty()) {
unordered_set < int > aux;
string str;
while (!s.empty()) {
if (aux.find(s.top().first) == aux.end()) {
aux.insert(s.top().first);
str += to_string(s.top().first);
str += " ";
}
if (aux.find(s.top().second) == aux.end()) {
aux.insert(s.top().second);
str += to_string(s.top().second);
str += " ";
}
s.pop();
}
str += '\n';
rasp.push_back(str);
}
}
return rasp;
}
// Functie bfs de ajutor pentru diametrul unui arbore
int grafNeorientat::bfsDarb(const int start, int& sosire) {
vector < int > rasp(noduri + 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;
sosire = i;
}
}
}
return rasp[sosire];
}
// Functie care returneaza diametrul unui arbore
int grafNeorientat::darb() {
int last = 0, aux;
aux = bfsDarb(1, last);
aux = bfsDarb(last, last);
return aux + 1;
}
// Functie care verifica daca un graf neorientat poate fi euler
bool grafNeorientat::isEuler() {
// Daca orice nod are gradul impar atunci graful nu poate fi eulerian
for (int i = 1; i < adiacenta.size(); i++) {
if (adiacenta[i].size() % 2 != 0) {
return 0;
}
}
return 1;
}
// Functie care returneaza ciclul euler al unui graf eulerian
vector<int> grafNeorientat::euler() {
// Algoritmul lui Hierholzer
// Se incepe dintr-un nod oarecare si se parcurge graful cam ca intr-un dfs pana ajungem din nou la nodul de inceput, numai ca stergem muchiile prin care trecem
// Acest lucru e garantat sa se intample pt ca graful e eulerien
// Dupa ce am ajuns inapoi, adaugam nodul de start la drumul eulerian final, si ne intoarcem in dfs pentru a gasi un nod care inca are muchii care pot fi accesate
// si incepem la fel ca inainte cu alt nod
// Acest lucru se bazeaza pe faptul ca un graf eulerian se poate descompune in cicluri disjuncte
stack<int> curent;
vector<int> raspuns;
// Se incepe cu un nod oarecare, 1 in cazul nostru
curent.push(1);
// Cat timp exista noduri in ciclul curent
while (!curent.empty()) {
// Se ia primul nod
int nod = curent.top();
// Se verifica daca are vecini
if (adiacenta[nod].size()) {
// Se ia un vecin si se baga in ciclul curent
int nod1 = adiacenta[nod].back();
curent.push(nod1);
// Se sterge muchia
adiacenta[nod].pop_back();
int i;
for (i = 0; i < adiacenta[nod1].size(); i++) {
if (adiacenta[nod1][i] == nod) {
break;
}
}
adiacenta[nod1].erase(adiacenta[nod1].begin() + i);
}
else {
// Daca nodul nu mai are niciun vecin accesibil, de intoarcem la nodul dinaintea lui poate are el
raspuns.push_back(nod);
curent.pop();
}
}
return raspuns;
}
// Functie pentru a gasi muchiile critice dintr-un graf, rezultatul va fi pus in rasp.
void grafNeorientat::dfsCriticalConnections(int tata, vector < int >& timp, vector < int >& rev, int& timpCurent, vector < vector < int >>& rasp, vector < int >& parinte) {
// Tarjan modificat
timpCurent++;
timp[tata] = timpCurent;
rev[tata] = timpCurent;
// Se tin minte timpii de intoarcere respectiv timpul de intalnire al fiecarui nod in arborele de dfs call
for (int fiu : adiacenta[tata]) {
// Tinem minte parintele direct din arborele dfs
parinte[fiu] = tata;
if (timp[fiu] == -1) {
// Cand descoperim un fiu nevizitat facem dfs
dfsCriticalConnections(fiu, timp, rev, timpCurent, rasp, parinte);
// Timpul de revenire al unei muchii este minimul dintre timpul de revenire curent si timpul de revenire al fiului,
// pt ca daca fiul are timp de revenire mai mic si tata il va putea accesa
rev[tata] = min(rev[tata], rev[fiu]);
if (rev[fiu] > timp[tata]) {
vector < int > aux;
aux.push_back(tata);
aux.push_back(fiu);
rasp.push_back(aux);
}
}
// Daca nodul e deja vizitat, atunci am detectat o muchie de intoarcere,
// si timpul de revenire al tatalui devine minimul dintre timpul actual de revenire (ca poate fi mai mic, cu o alta muchie gasita deja)
// si timpul de gasire al fiului
// Se verifica ca muchia sa nu fie una prezenta deja, sa nu fie una care sa mearga in fata in arborele dfs
else if (parinte[tata] != fiu) {
rev[tata] = min(rev[tata], timp[fiu]);
}
}
}
// Functie care returneaza muchiile critice ale unui graf neorientat
vector < vector < int >> grafNeorientat::criticalConnections() {
vector < int > timp(noduri + 1, -1), rev(noduri + 1), parinte(noduri + 1);
vector < vector < int >> rasp;
int timpo = 0;
// Se face dfs pt fiecare componenta conexa
for (int i = 1; i <= noduri; i++) {
if (timp[i] == -1) {
dfsCriticalConnections(i, timp, rev, timpo, rasp, parinte);
}
}
return rasp;
}
// Functii pentru clasa graf orientat
// Determina componentele tare conexe ale unui graf orientat, si le pune in 'rasp'.
void grafOrientat::dfsCtc(int tata, vector < int >& timp, vector < int >& rev, stack < int >& s, int& timpCurent, vector < string >& rasp, unordered_set < int >& check) {
// Tarjan
timpCurent++;
timp[tata] = timpCurent;
rev[tata] = timpCurent;
s.push(tata);
check.insert(tata);
// Se tin minte timpii de intoarcere respectiv timpul de intalnire al fiecarui nod in arborele de dfs call
for (int fiu : adiacenta[tata]) {
if (timp[fiu] == -1) {
// Cand descoperim un fiu nevizitat facem dfs
dfsCtc(fiu, timp, rev, s, timpCurent, rasp, check);
// Timpul de revenire al unei muchii este minimul dintre timpul de revenire curent si timpul de revenire al fiului,
// pt ca daca fiul are timp de revenire mai mic si tata il va putea accesa
rev[tata] = min(rev[tata], rev[fiu]);
}
// Daca nodul e deja vizitat, atunci am detectat o muchie de intoarcere,
// si timpul de revenire al tatalui devine minimul dintre timpul actual de revenire (ca poate fi mai mic, cu o alta muchie gasita deja)
// si timpul de gasire al fiului
else if (check.find(fiu) != check.end()) {
rev[tata] = min(rev[tata], timp[fiu]);
}
}
// Dupa ce se parcurg toti descendentii tatalui, verificam daca timpul de revenire al tatalui este egal cu timpul de intalnire al sau.
// Daca sunt egale, exista doua cazuri, ori tatal face parte dintr-o componenta tare conexa cu descendenti de-ai sai bagati deja in stack,
// ori el este o componenta tare conexa singur.
// Se vor salva nodurile rezultate in stringuri. Check tine minte daca un element e in stack sau nu, caci daca nu e poate forma o componenta tare conexa cu altcineva
if (timp[tata] == rev[tata]) {
string aux = "";
while (s.top() != tata) {
aux += to_string(s.top());
aux += " ";
check.erase(s.top());
s.pop();
}
aux += to_string(s.top());
aux += " ";
check.erase(s.top());
s.pop();
aux += '\n';
rasp.push_back(aux);
}
}
// Functie care returneaza componentele tare conexe ale unui graf orientat.
vector < string > grafOrientat::ctc() {
vector < int > timp(noduri + 1, -1), rev(noduri + 1);
unordered_set < int > check;
stack < int > s;
vector < string > rasp;
int timpo = 0;
// Se porneste dfs-ul din toate componentele conexe, si apoi se adauga la raspuns si ce a mai ramas in stack, pt ca si ce ramane va forma o componenta biconexa
for (int i = 1; i <= noduri; i++) {
if (timp[i] == -1) {
dfsCtc(i, timp, rev, s, timpo, rasp, check);
}
}
return rasp;
}
// Functie pentru a sorta topologim un graf. Ordinea va fi returnata in vectorul 'res'.
void grafOrientat::dfsSortaret(int tata, vector < int >& vis, vector < int >& res) {
// Se face dfs cu recursivitate
for (int fiu : adiacenta[tata]) {
if (!vis[fiu]) {
vis[fiu] = 1;
dfsSortaret(fiu, vis, res);
}
}
// Cand se termina de cautat in fii unui nod, se adauga la raspuns, pt ca inseamna ca nu mai depinde nimeni de el
res.push_back(tata);
}
// Functie care returneaza o sortare topologica a unui graf orientat
vector < int > grafOrientat::sortaret() {
vector < int > vis(this->noduri + 1);
vector < int > res;
// Se face dfs pt fiecare componenta conexa
for (int i = 1; i <= this->noduri; i++) {
if (vis[i] == 0) {
vis[i] = 1;
dfsSortaret(i, vis, res);
}
}
return res;
}
// Functii pentru clasa graf neorientat ponderat
// Functie care creeaza un graf partial de cost minim pornind de la un graf ponderat
vector< vector< int >> grafNeorientatPonderat::apm(vector< vector< int >>& much, ostream& out) {
// Kruskal
// Se vor adauga muchii in ordine crescatoare care sa nu inchida un ciclu in graf
// Vom realiza asta retinand tatal fiecarui nod din arborii partiali formati pana la un moment dat. Astea vor fi puse in vectorul tata
vector< int > tata(noduri + 1);
vector< vector < int >> rasp;
// Sortam muchiile dupa cost
sort(much.begin(), much.end(), [](vector<int> a, vector<int> b) {
return a[2] < b[2];
});
int i = 0, j = 0;
long long s = 0;
// Initializam vectorul tata, fiecarui nod ii atribuim tata chiar pe el, pentru a ne da seama cand nodul nu are de fapt tata
for (int i = 1; i < tata.size(); i++) {
tata[i] = i;
}
// Ciclam prin muchii pana cand am adaugat suficiente ca graful sa fie conex
while (i < this->noduri - 1) {
// Se iau nodurile care formeaza o muchie
int nod1 = much[j][0], nod2 = much[j][1];
int tata1 = nod1, tata2 = nod2;
// Se gaseste radacina arborilor partiali din care fac parte nodurile
while (tata1 != tata[tata1]) {
tata1 = tata[tata1];
}
while (tata2 != tata[tata2]) {
tata2 = tata[tata2];
}
// Daca 2 noduri fac parte din arbori diferiti, adica radacinile lor sunt diferite, am gasit o muchie pe care s-o adaugam in arborele partial de cost minim
if (tata1 != tata2) {
// Adaugam costul muchiei adaugate la costul final
s += much[j][2];
// Unim 2 arbori partiali
// Unim mereu arborele cu radacina mai mare dpdv lexicografic cu arborele cu radacina mai mica, pentru a-i avea intr-o anumita ordine si pentru a fi sanse mai mari sa se lege arbori
// Direct de radacina, si deci sa avem inaltimi mai mici ale arborilor
if (tata[tata1] < tata[tata2]) {
tata[tata1] = tata[tata2];
}
else {
tata[tata2] = tata[tata1];
}
// Adaugam muchia la raspuns
rasp.push_back({ nod1, nod2 });
i++;
}
j++;
}
// Afisare suma si numar muchii din graf
out << s << '\n' << this->noduri - 1 << '\n';
return rasp;
}
// Functie care returneaza drumul minim de la nodul 1 la fiecare nod din graf neorientat. Merge si pe costuri negative
unordered_map<int, int> grafNeorientatPonderat::bellmanFord() {
// Map sa tinem minte costul pana la fiecare mod
unordered_map<int, int> m;
// Queue pentru a tine minte nodurile care ar putea fi relaxate
queue<int> q;
// De cate ori a fost relaxat un nod
vector<int> cnt(noduri + 1);
// Daca un nod este in queue sau nu
unordered_set<int> check;
// Incepem de la nodul 1
m[1] = 0;
q.push(1);
check.insert(1);
// Cat timp coada are noduri in ea, parcurgem nodurile din coada
while (!q.empty()) {
// Luam nodul din capul cozii
int nod1 = q.front();
check.erase(nod1);
q.pop();
// Parcurgem lista de adiacenta a nodului pe care l-am luat
for (pair<int, int> muchie : adiacentaPonderata[nod1]) {
// Retinem nodurile si costurile la care duc muchiile din nod
int nod2 = muchie.first, cost = muchie.second;
// Daca un nod nu are cost sau costul pe care il avem deja e mai mare decat costul pe care l-am forma cu noua muchie gasita, facem update
if (m.find(nod2) == m.end() || m[nod2] > m[nod1] + cost) {
// Updatam costul
m[nod2] = m[nod1] + cost;
// Daca al doilea nod nu este in queue, il bagam, pt ca stim ca exista posibiltatea ca vecinii lui sa poata fi relaxati
if (check.find(nod2) == check.end()) {
q.push(nod2);
check.insert(nod2);
cnt[nod2]++;
// Daca un nod a fost relaxat de mai multe ori decat sunt noduri, e clar ca exista un ciclu care reduce mereu costul
if (cnt[nod2] > noduri) {
// Returnam un map gol pentru a semnala acest lucru
m.clear();
return m;
}
}
}
}
}
return m;
}
// Functii pentru clasa graf orientat ponderat
// Functie care returneaza drumul minim de la nodul 1 la fiecare nod din graf orientat
unordered_map<int, int> grafOrientatPonderat::dijkstra() {
// Aici tinem distantele
unordered_map<int, int> m;
// Priority queue (heap) pentru a tine minte mereu nodul la care se poate ajunge cel mai rapid
priority_queue<vector<int>> p;
// Tinem minte daca nodul a fost deja vizitat
vector<bool> vis(noduri + 1, false);
// Stim ca incepem din nodul 1 mereu deci distanta va fi 0, si il adaugam in heap
m[1] = 0;
p.push({ 0, 1 });
// Mergem prin priority queue pana cand nu mai avem ce lua din el
while (!p.empty()) {
// Luam cel mai mic nod
int curNod = p.top()[1];
p.pop();
// Daca nodul nu a fost deja analizat, incepem analizarea lui
if (!vis[curNod]) {
vis[curNod] = true;
// Ne uitam la vecinii lui
for (auto i : adiacentaPonderata[curNod]) {
int nod = i.first, cost = i.second;
// Daca distanta pana la nod nu a fost inca determinata sau e mai mare decat lungimea calculata acum, o modificam
if (m.find(nod) == m.end() || m[nod] > m[curNod] + cost) {
m[nod] = m[curNod] + cost;
p.push({ -(m[nod]), nod });
}
}
}
}
return m;
}
// Functie care returneaza pornind de la matricea de adiacenta cu costuri cel mai scurt drum de la fiecare nod la fiecare nod
vector<vector<int>> grafOrientatPonderat::royFloyd(vector<vector<int>> rasp) {
// Incearca sa gaseasca pentru fiecare 2 noduri i si j, un nod k prin care daca trecem sa devina costul de la i la j mai mic
for (int k = 1; k <= noduri; k++) {
for (int i = 1; i <= noduri; i++) {
for (int j = 1; j <= noduri; j++) {
// Verificam conditia enuntata mai sus. Avem grija ca i si j sa fie accesibile din k iar i si j sa nu fie chiar acelasi nod
if ((rasp[i][k] + rasp[k][j] < rasp[i][j] || rasp[i][j] == 0) && rasp[k][j] && rasp[i][k] && i != j) {
rasp[i][j] = rasp[i][k] + rasp[k][j];
}
}
}
}
return rasp;
}
// Functie care returneaza ciclul hamiltonian de cost minim al unui graf hamiltonian
int grafOrientatPonderat::hamilton(vector<vector<int>> cost)
{
#define hamiltonHelper 100000000
const int constrangere1 = 300000;
const int constrangere2 = 20;
int raspuns = hamiltonHelper;
vector<vector<int>> matrice(constrangere1, vector<int>(constrangere2));
for (int i = 0; i < 1 << noduri; i++) {
for (int j = 0; j < noduri; j++) {
matrice[i][j] = hamiltonHelper;
}
}
matrice[1][0] = 0;
for (int i = 0; i < 1 << noduri; i++) {
for (int j = 0; j < noduri; j++) {
if (i & (1 << j)) {
for (int nod : adiacenta[j]) {
if (i & (1 << nod)) {
matrice[i][j] = min(matrice[i][j], matrice[i ^ (1 << j)][nod] + cost[nod][j]);
}
}
}
}
}
for (int nod : adiacenta[0]) {
raspuns = min(raspuns, matrice[(1 << noduri) - 1][nod] + cost[nod][0]);
}
return raspuns;
}
// Functii pentru clasa retea
// Functie ajutatoare bfs pentru maxflow
bool retea::auxBfs(const int start, vector<int>& parinti, vector<vector<int>> matrice, vector<vector<int>> cost) {
vector < int > vis(noduri + 1);
queue < int > q;
q.push(start);
vis[1] = 1;
// 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] && cost[curr][i] > matrice[curr][i]) {
parinti[i] = curr;
q.push(i);
vis[i] = 1;
}
}
}
return vis[noduri];
}
// Functie care primeste o retea si returneaza fluxul maxim care poate fi transmis de la sursa la desinatie prin retea
int retea::maxflow() {
vector<int> parinti(noduri + 1);
vector<vector<int>> matrice(noduri + 1, vector<int>(noduri + 1));
int m = 0, start = 1, sosire = noduri, currm = INT_MAX;
while (this->auxBfs(start, parinti, matrice, cost)) {
for (auto p : adiacenta[noduri]) {
if (cost[p][noduri] > matrice[p][noduri]) {
parinti[noduri] = p;
currm = cost[p][sosire] - matrice[p][sosire];
int j;
for (int i = p; i != 1; i = parinti[i]) {
j = parinti[i];
currm = min(currm, cost[j][i] - matrice[j][i]);
}
matrice[p][sosire] += currm;
matrice[sosire][p] -= currm;
for (int i = p; i != 1; i = parinti[i]) {
j = parinti[i];
matrice[j][i] += currm;
matrice[i][j] -= currm;
}
m += currm;
}
}
}
return m;
}
// Functii pentru clasa graf bipartit
// Dfs modificat pentru algoritmul de cuplaj. Returneaza true daca exista un drum de la un nod dat la un nod care poate fi inclus in cuplaj.
bool grafBipartit::dfsCuplaj(int start, vector<int>& perecheStanga, vector<int>& perecheDreapta, vector<int>& distanta) {
if (!start) {
return true;
}
for (int nod : adiacenta[start]) {
// Daca nodurile sunt consecutive in bfs, mergem mai departe in dfs
if (distanta[perecheDreapta[nod]] == distanta[start] + 1) {
if (dfsCuplaj(perecheDreapta[nod], perecheStanga, perecheDreapta, distanta)) {
// Daca s-a gasit un drum bun, atunci s-a gasit o pereche de noduri
perecheDreapta[nod] = start;
perecheStanga[start] = nod;
return true;
}
}
}
// Daca nu s-a gasit un drum se ajunge aici si atunci distanta nodului de start va fi infinit pentru ca nu exista drum bun pornind de la el
distanta[start] = INT_MAX;
return false;
}
// Bfs modificat pentru algoritmul de cuplaj. Returneaza true daca exista un drum oarecare la un nod care poate fi inclus in cuplaj.
bool grafBipartit::bfsCuplaj(vector<int>& perecheStanga, vector<int>& perecheDreapta, vector<int>& distanta) {
queue<int> q;
// Initial bagam toate nodurile libere in queue ca sa fie procesate de bfs
for (int nod = 1; nod <= stanga; nod++) {
if (perecheStanga[nod]) {
distanta[nod] = INT_MAX;
}
else {
q.push(nod);
distanta[nod] = 0;
}
}
distanta[0] = INT_MAX;
// Se face bfs
while (!q.empty()) {
int nod1 = q.front();
q.pop();
// Daca un nod poate micsora distanta drumului ii parcurgem vecinii
if (distanta[nod1] < distanta[0]) {
for (int nod2 : adiacenta[nod1]) {
// Daca pereche nodului vecin nu a fost considerat inca il bagam pe drum
if (distanta[perecheDreapta[nod2]] == INT_MAX) {
distanta[perecheDreapta[nod2]] = distanta[nod1] + 1;
q.push(perecheDreapta[nod2]);
}
}
}
}
// Se returneaza daca exista vreun drum, adica daca s-a schimbat timpul drumului
return (distanta[0] != INT_MAX);
}
// Algoritmul Hopcroft-Karp pentru a gasi cuplajul maxim intr-un graf bipartit// Algoritmul Hopcroft-Karp pentru a gasi cuplajul maxim intr-un graf bipartit
vector<pair<int, int>> grafBipartit::cuplaj()
{
// Se cauta un drum care alterneaza muchii care pot fi folosite la cuplaj si muchii care nu. Drumul incepe si se termina in noduri care pot fi adaugate la cuplaj
// Se tin minte perechile nodurilor din dreapta si stanga grafului, si distanta de la nodurile din stanga pe drumuri
vector<int> perecheStanga(stanga + 1);
vector<int> perecheDreapta(dreapta + 1);
vector<int> distanta(stanga + 1);
// Cat timp exista un drum care poate fi gasit
while (bfsCuplaj(perecheStanga, perecheDreapta, distanta)) {
// Gasim un nod liber
for (int i = 1; i <= stanga; i++) {
if (!perecheStanga[i]) {
// Cautam drum pornind de la el
dfsCuplaj(i, perecheStanga, perecheDreapta, distanta);
}
}
}
// Se construieste raspunsul
vector<pair<int, int>> raspuns;
for (int i = 1; i <= stanga; i++) {
if (perecheStanga[i]) {
raspuns.push_back(make_pair(i, perecheStanga[i]));
}
}
return raspuns;
}
// Functii care nu se apeleaza pe un graf
// Functie care primeste un vector care contine gradele nodurilor unui graf, si determina daca se poate forma un graf cu ele sau nu. Este in afara clasei pentru ca nu face operatii pe un graf
bool havelHakimi(vector < int >& a) {
// Mai intai se sorteaza vectorul ca sa avem mereu nodul cu cel mai mare grad primul
sort(a.begin(), a.end(), [](int m, int n) {
return m > n;
});
int x = a[0];
// Daca mai e un singur nod in vector cu grad nenul, evident, nu se va putea face graf cu el
if (a.size() == 1 && x >= 1) {
return false;
}
// Daca primul nod e 0, tinand cont ca vectorul e sortat crescator, atunci toate sunt 0 si e bine, se poate forma graf
if (x == 0) {
return true;
}
// Se sterge primul element din vector, ii facem legaturile
a.erase(a.begin() + 0);
// Daca nodul are grad mai mare decat sunt legaturi posibile atunci e clar ca nu e posibil sa facem graf
if (x > a.size()) {
return false;
}
// 'Conectam' primul nod la urmatoarele noduri din vector, cate ne spune gradul lui
for (int i = 0; i < x; i++) {
a[i]--;
// Daca un nod ajunge cu gradul pe minus, e clar ca nu se paote face graf
if (a[i] < 0) {
return false;
}
}
// Apelam recursiv cu noul vector format
return havelHakimi(a);
}
// Functie care poate face 2 actiuni, uneste 2 paduri sau afiseaza daca 2 noduri sunt in aceeasi padure sau nu
void disjoint(istream& in, ostream& out) {
int n, m;
in >> n >> m;
// Vectorul in care tinem minte tatii, initial tatal lui i va fi chiar i, pt totul e deconectat
vector< int > tata(n + 1);
for (int i = 1; i < tata.size(); i++) {
tata[i] = i;
}
// Mergem prin operatii
for (int i = 0; i < m; i++) {
int tip, nod1, nod2;
in >> tip >> nod1 >> nod2;
int tata1 = nod1, tata2 = nod2;
// Descoperim care sunt radacinile arborilor nodurilor de care avem nevoie
while (tata[tata1] != tata1) {
tata1 = tata[tata1];
}
while (tata[tata2] != tata2) {
tata2 = tata[tata2];
}
// Vedem de ce tip e operatia
if (tip == 1) {
// Se unesc 2 arbori
tata[tata1] = tata[tata2];
}
else {
// Daca radacinile celor 2 arbori corespunzatori nodurilor date coincid, e clar ca si arborii coincid
if (tata1 == tata2) {
out << "DA\n";
}
else {
out << "NU\n";
}
// Dupa ce facem actiunea asta, se face o euristica, si anume unim toate nodurile din arborii tocmai accesati chiar de radacina arborilor in care sunt
while (tata[nod1] != nod1) {
tata[nod1] = tata1;
nod1 = tata[nod1];
}
while (tata[nod2] != nod2) {
tata[nod2] = tata2;
nod2 = tata[nod2];
}
}
}
}
// Functii in care se face citirea si afisarea specifica fiecarei probleme
void bfsDriver() {
// https://infoarena.ro/problema/bfs
// Citire
ifstream in("bfs.in");
ofstream out("bfs.out");
int n, m, s;
in >> n >> m >> s;
vector<vector<int>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
adiacenta[aux1].push_back(aux2);
}
grafOrientat x(adiacenta, n, m);
// Afisare
vector < int > rasp = x.dfs(s);
for (int i = 1; i <= n; i++) {
out << rasp[i] << " ";
}
in.close();
out.close();
}
void componenteConexeDriver() {
// https://infoarena.ro/problema/dfs
// Citire
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m;
in >> n >> m;
vector<vector<int>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
adiacenta[aux1].push_back(aux2);
adiacenta[aux2].push_back(aux1);
}
grafNeorientat x(adiacenta, n, m);
// Afisare
out << x.componenteConexe();
in.close();
out.close();
}
void biconexDriver() {
// https://infoarena.ro/problema/biconex
// Citire
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m;
in >> n >> m;
vector<vector<int>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
adiacenta[aux1].push_back(aux2);
adiacenta[aux2].push_back(aux1);
}
grafNeorientat x(adiacenta, n, m);
// Afisare
vector < string > fin = x.biconex();
out << fin.size() << '\n';
for (string i : fin) {
out << i;
}
in.close();
out.close();
}
void ctcDriver() {
// https://infoarena.ro/problema/ctc
// Citire
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m;
in >> n >> m;
vector<vector<int>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
adiacenta[aux1].push_back(aux2);
}
grafOrientat x(adiacenta, n, m);
// Afisare
vector < string > fin = x.ctc();
out << fin.size() << '\n';
for (string i : fin) {
out << i;
}
in.close();
out.close();
}
void sortaretDriver() {
// https://infoarena.ro/problema/sortaret
// Citire
ifstream in("sortaret.in");
ofstream out("sortaret.out");
int n, m;
in >> n >> m;
vector<vector<int>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
adiacenta[aux1].push_back(aux2);
}
grafOrientat x(adiacenta, n, m);
// Afisare
// Citim vectorul invers fata de cum l-am creat, pt ca ultimul nod care e accesat e nodul cu cele mai multe dependente
vector < int > res = x.sortaret();
for (int i = res.size() - 1; i >= 0; i--) {
out << res[i] << " ";
}
in.close();
out.close();
}
void havelHakimiDriver() {
// Citire
ifstream in("havelhakimi.in");
ofstream out("havelhakimi.out");
int n, k = 1;
in >> n;
vector < int > a;
for (int i = 0; i < n; i++) {
int aux;
in >> aux;
a.push_back(aux);
}
// Afisare
out << havelHakimi(a);
in.close();
out.close();
}
void criticalConnectionsDriver() {
// https://leetcode.com/problems/critical-connections-in-a-network/
// Citire
int n, m;
cin >> n >> m;
vector<vector<int>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2;
cin >> aux1 >> aux2;
adiacenta[aux1].push_back(aux2);
adiacenta[aux2].push_back(aux1);
}
grafNeorientat x(adiacenta, n, m);
// Afisare
vector < vector < int >> fin = x.criticalConnections();
for (auto i : fin) {
for (auto j : i) {
cout << j << " ";
}
}
}
void apmDriver() {
// https://infoarena.ro/problema/apm
// Citire
ifstream in("apm.in");
ofstream out("apm.out");
int n, m;
in >> n >> m;
grafNeorientatPonderat x(n, m);
vector< vector< int >> much;
for (int i = 0; i < m; i++) {
int aux1, aux2, aux3;
in >> aux1 >> aux2 >> aux3;
much.push_back({ aux1, aux2, aux3 });
}
// Afisare
vector< vector< int >> v = x.apm(much, out);
for (auto i : v) {
out << i[0] << " " << i[1] << "\n";
}
in.close();
out.close();
}
void disjointDriver() {
// // https://infoarena.ro/problema/disjoint
// Citire
ifstream in("disjoint.in");
ofstream out("disjoint.out");
// Apelare
disjoint(in, out);
in.close();
out.close();
}
void dijkstraDriver() {
// https://infoarena.ro/problema/dijkstra
// Citire
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n, m;
in >> n >> m;
vector< vector< pair< int, int >>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2, aux3;
in >> aux1 >> aux2 >> aux3;
adiacenta[aux1].push_back(make_pair(aux2, aux3));
}
grafOrientatPonderat x(adiacenta, n, m);
// Afisare
unordered_map<int, int> v = x.dijkstra();
for (int i = 2; i <= n; i++) {
if (v.find(i) == v.end()) {
out << "0 ";
}
else {
out << v[i] << " ";
}
}
in.close();
out.close();
}
void bellmanfordDriver() {
// https://infoarena.ro/problema/bellmanFord
// Citire
ifstream in("bellmanFord.in");
ofstream out("bellmanFord.out");
int n, m;
in >> n >> m;
vector<vector<pair<int, int>>> muchii(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2, aux3;
in >> aux1 >> aux2 >> aux3;
muchii[aux1].push_back(make_pair(aux2, aux3));
}
grafNeorientatPonderat x(muchii, n, m);
// Afisare
unordered_map<int, int> v = x.bellmanFord();
if (v.empty()) {
out << "Ciclu negativ!";
}
else {
for (int i = 2; i <= n; i++) {
out << v[i] << " ";
}
}
in.close();
out.close();
}
void maxflowDriver() {
// https://infoarena.ro/problema/maxflow
// Citire
ifstream in("maxflow.in");
ofstream out("maxflow.out");
int n, m;
in >> n >> m;
vector< vector< pair< int, int >>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2, aux3;
in >> aux1 >> aux2 >> aux3;
adiacenta[aux1].push_back(make_pair(aux2, aux3));
}
retea x(adiacenta, n, m);
// Afisare
out << x.maxflow();
in.close();
out.close();
}
void royfloydDriver() {
// https://infoarena.ro/problema/royFloyd
// Citire
ifstream in("royfloyd.in");
ofstream out("royfloyd.out");
int n, m = 0;
in >> n;
vector<vector<int>> matrice(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
in >> matrice[i][j];
}
}
grafOrientatPonderat x(n, m);
// Afisare
vector<vector<int>> rasp = x.royFloyd(matrice);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
out << rasp[i][j] << " ";
}
out << '\n';
}
in.close();
out.close();
}
void darbDriver() {
// https://infoarena.ro/problema/darb
// Citire
ifstream in("darb.in");
ofstream out("darb.out");
int n, m = 0, a, b;
in >> n;
vector < vector < int >> listaAdiacenta(n + 1);
while (in >> a >> b) {
listaAdiacenta[a].push_back(b);
listaAdiacenta[b].push_back(a);
}
grafNeorientat x(listaAdiacenta, n, m);
// Afisare
out << x.darb();
in.close();
out.close();
}
void eulerDriver() {
// https://infoarena.ro/problema/ciclueuler
// Citire
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int n, m;
in >> n >> m;
vector<vector<int>> adiacenta(n + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
adiacenta[aux1].push_back(aux2);
adiacenta[aux2].push_back(aux1);
}
grafNeorientat x(adiacenta, n, m);
if (!x.isEuler()) {
out << -1;
return;
}
// Afisare
vector<int> raspuns = x.euler();
for (int i = 0; i < raspuns.size() - 1; i++) {
out << raspuns[i] << " ";
}
in.close();
out.close();
}
void hamiltonDriver() {
// https://infoarena.ro/problema/hamilton
// Citire
ifstream in("hamilton.in");
ofstream out("hamilton.out");
int n, m;
in >> n >> m;
vector<vector<int>> adiacenta(n + 1);
vector<vector<int>> cost(n + 1, vector<int>(n + 1, INT_MAX));
for (int i = 1; i <= m; i++) {
int aux1, aux2, aux3;
in >> aux1 >> aux2 >> aux3;
adiacenta[aux2].push_back(aux1);
cost[aux1][aux2] = aux3;
}
grafOrientatPonderat x(adiacenta, n, m);
// Afisare
int raspuns = x.hamilton(cost);
if (raspuns == hamiltonHelper) {
out << "Nu exista solutie";
}
else {
out << raspuns;
}
in.close();
out.close();
}
void cuplajDriver() {
// https://infoarena.ro/problema/cuplaj
// Citire
ifstream in("cuplaj.in");
ofstream out("cuplaj.out");
int l, r, m;
in >> l >> r >> m;
vector<vector<int>> adiacenta(l + r + 1);
for (int i = 0; i < m; i++) {
int aux1, aux2;
in >> aux1 >> aux2;
adiacenta[aux1].push_back(aux2);
}
grafBipartit x(adiacenta, l, r, m);
// Afisare
vector<pair<int, int>> v = x.cuplaj();
out << v.size() << '\n';
for (auto i : v) {
out << i.first << ' ' << i.second << '\n';
}
in.close();
out.close();
}
int main() {
// Se apeleaza functia corespunzatoare problemei
componenteConexeDriver();
return 0;
}
Tiganus Alexandru redikus