#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
class Graph {
public:
enum NodeSortOrder {
ASCENDING_BY_NODE_KEY,
DESCENDING_BY_NODE_KEY,
UNDEFINED
};
struct GraphOpts {
bool zeroIndexed; // daca nodurile sunt indexate de la zero sau nu
bool directed; // daca este graf orientat sau nu
bool debug; // Daca este setat la true, atunci printeaza informatii aditionale pentru debugging
NodeSortOrder nodeSortOrder;
GraphOpts(
bool zeroIndexed = false,
bool directed = false,
bool debug = false,
NodeSortOrder nodeSortOrder = UNDEFINED
): zeroIndexed(zeroIndexed), directed(directed), debug(debug), nodeSortOrder(nodeSortOrder) {
}
};
template <typename T = int>
struct NodeInfoContainer {
vector<T> nodeInfo;
};
struct EdgeInfo {
int source;
int destination;
double weight;
};
protected:
GraphOpts Opts;
int N = 0; // numarul de noduri
int M = 0; // numarul de muchii
// Lista de adiacenta a grafului, un vector de vectori ce au ca elemente un pair de int si double
// Primul element al fiecarei perechi reprezinta nodul destinatie, iar al doilea element al perechii
// reprezinta costul acelei muchii (sau capacitatea ei, in contexul algoritmului pt determinarea fluxului minim / maxim)
vector<vector<pair<int, double>>> adjList;
// Functie ce returneaza dimensiunea pe care trebuie sa o aiba containerul ce retine informatii despre toate nodurile din graf.
// Daca nodurile grafului sunt indexate de la 0, atunci acesta dimensiune este fix N, deoarece trebuie retinute informatii despre nodurile 0...N-1
// In schimb, daca nodurile sunt indexate de la 1, atunci acesta trebuie sa aiba dimensiunea N+1, pt ca indexarea in container incepe de la 0 dar in graf nodul 0 nu exista,
// primul nod fiind 1
int getNodesContainerSize() {
return N + (this->Opts.zeroIndexed ? 0 : 1);
}
int getFirstNodeIndex() const {
return this->Opts.zeroIndexed ? 0 : 1;
}
int getLastNodeIndex() const{
return this->Opts.zeroIndexed ? N-1 : N;
}
// Functie ce afiseaza lista de adiacenta a grafului, inserand datele intr-un stream de iesire dat ca parametru (daca parametrul nu e furnizat, va fi default stream-ul standard de iesire adica cout)
void printAdjList(ostream& os = cout) const {
int startIndex = this->getFirstNodeIndex();
int endIndex = this->getLastNodeIndex();
for(int i = startIndex; i <= endIndex; i++) {
os << i << ": ";
for(int j = 0; j < adjList[i].size(); j++) {
os << adjList[i][j].first << " (w = " << adjList[i][j].second << ") ";
}
os << "\n";
}
}
// Functie utilitara ce primeste ca parametru rezultatul in care sa scrie nodurile parcurse in ordine DF, vectorul ce retine starea nodurile in raport cu faptul ca au fost vizitate sau nu si nodul curent
void _DFSUtil(vector<int>& result, vector<bool>& visited, int currentNode, bool postOrder = false) {
visited[currentNode] = true;
if(!postOrder) {
result.push_back(currentNode);
}
for(int j = 0; j < adjList[currentNode].size(); j++) {
int neighbor = adjList[currentNode][j].first;
if(!visited[neighbor]) {
_DFSUtil(result, visited, neighbor, postOrder);
}
}
if(postOrder) {
result.push_back(currentNode);
}
}
public:
Graph(int N = 0, int M = 0, vector<EdgeInfo> edges = {}, Graph::GraphOpts opts = {false, false, false}) {
this->N = N;
this->M = M;
this->Opts = opts;
for(auto it: edges) {
this->addEdge(it.source, it.destination, it.weight);
}
}
Graph(int N = 0, int M = 0, vector<vector<int>> edges = {}, Graph::GraphOpts opts = {false, false, false}) {
this->N = N;
this->M = M;
this->Opts = opts;
for(auto it: edges) {
this->addEdge(it[0], it[1], it.size() > 2 ? it[2] : 0);
}
}
Graph(vector<EdgeInfo> edges) {
for(auto it: edges) {
this->addEdge(it.source, it.destination, it.weight);
}
}
Graph(vector<vector<int>> edges) {
for(auto it: edges) {
this->addEdge(it[0], it[1], it.size() > 2 ? it[2] : 0);
}
}
Graph(Graph::GraphOpts opts = {false, false, false}) {
this->Opts = opts;
}
// Functie ce adauga o muchie la graf
/** Functia accepta ca parametrii sursa, destinatia, costul muchiei si alti parametrii aditionali care sunt optionali:
* - sortNodes -> daca este true, in lista de adiacenta a fiecarui nod vecinii vor fi sortati in ordine crescatoare. Sortarea se va face prin
* insertion sort, noul vecin inserandu-se de fiecare data pe pozitia care pastreaza ordinea sortarii
*/
void addEdge(int source, int destination, double weight, bool bidirectional = false) {
// Ne asiguram exista suficient spatiu in lista de adiacenta a grafului pentru a adauga vecini ai nodului source
// Daca nodul sursa / destinatie este mai mare sau egal cu lungimea listei de adiacenta, atunci folosim functia STL resize care
// scaleaza containerul astfel incat are source + 1 elemente
if(max(source, destination) >= adjList.size()) {
adjList.resize(max(source, destination) + 1);
}
int insertionPosition = adjList[source].size();
if(this->Opts.nodeSortOrder == ASCENDING_BY_NODE_KEY) {
for(int pos = 0; pos < adjList[source].size(); ++pos) {
if(destination <= adjList[source][pos].first) {
insertionPosition = pos;
break;
}
}
}
// Introducem in lista de adiacenta a nodului source o pereche formata din celalalt capat al muchiei (destinatia) si costul asociat muchiei
// la pozitia insertionPosition, care in functie de optiunea sortNodes va fi sfarsitul listei (echivalent push_back) sau pozitia care
// pastreaza lista sortata
adjList[source].insert(adjList[source].begin() + insertionPosition, make_pair(destination, weight));
// Actualizam numarul de noduri daca este cazul. Daca nodurile sunt indexate de la 0, atunci trebuie sa adaugam 1 la nodul sursa (ex atunci cand nodul sursa
//este egal cu 5, de fapt exista 6 noduri)
N = max(N, max(source, destination) + (this->Opts.zeroIndexed ? 1: 0));
// Actualizam nr de muchii
++M;
// Informatii aditionale de debugging, in cazul care debug este setat la true in optiunile grafului
if(this->Opts.debug) {
printf("Added edge (%d %d) to the graph, bidirectional = %i\n", source, destination, bidirectional);
printf("Source = %d, Dest = %d, N = %d\n", source, destination, N);
cout << "opts.zeroIndexed = " << this->Opts.zeroIndexed << "\n";
}
// Daca argumentul bidirectional a fost setat la true sau a fost specificat in optiunile grafului ca este neorientat,
// atunci adaugam automat si cealalta muchie
if(bidirectional || !this->Opts.directed) {
if(destination >= adjList.size()) {
adjList.resize(destination + 1);
}
insertionPosition = adjList[destination].size();
if(this->Opts.nodeSortOrder == ASCENDING_BY_NODE_KEY) {
for(int pos = 0; pos < adjList[destination].size(); ++pos) {
if(source <= adjList[destination][pos].first) {
insertionPosition = pos;
break;
}
}
}
adjList[destination].insert(adjList[destination].begin() + insertionPosition, make_pair(source, weight));
N = max(N, destination + (this->Opts.zeroIndexed ? 1: 0) );
++M;
if(this->Opts.debug) {
printf(
"Added edge (%d %d) to the graph because bidirectional is set to true or the graph is undirected, bidirectional = %i\n",
destination,
source,
bidirectional
);
printf("Source = %d, Dest = %d, N = %d\n", destination, source, N);
cout << "opts.zeroIndexed = " << this->Opts.zeroIndexed << "\n";
}
}
}
// Getter pt numarul de noduri din graf
int getN() {
return this->N;
}
// Getter pt numarul de muchii din graf
int getM() {
return this->M;
}
// Getter pt optiunile grafului
GraphOpts getGraphOpts() {
return this->Opts;
}
NodeInfoContainer<double> dijkstra(int sourceNode) {
// Functia calculeaza distanta minima dintre nodul sourceNode si toate celealte noduri, utilizand algoritmul lui Dijkstra.
// Pentru fiecare dintre noduri, se retine distanta minima de la nodul sursa la acesta (vectorul fiind si valoarea returnata de functie).
// Initial, distanta de la sursa catre noduri nu este calculata, motiv pentru care ii vom asigna o valoare speciala.
// In majoritatea implementarilor se foloseste conceptul de initializare a distantei cu "Infinit" (cel mai adesea utilizandu-se o constanta precum INT_MAX).
// Pentru ca stim faptul ca algoritmul nu va fi utilizat pentru a determina path-uri minime pe grafuri cu muchii de costuri negative si pentru ca algoritmul
// sa functioneze cu costuri cat mai mari, distanta initiala va fi initializata cu -1 in loc de INT_MAX. Astfel, atunci cand dam de o distanta egala cu -1,
// vom sti cu siguranta nu a fost calculata inca pentru acel nod.
// Asadar, initial, vectorul de distante (de lungime N), va avea toate elementele initializate cu -1 (pentru ca distanta catre ele nu s-a calculat inca)
vector<double> minDistaceFromSourceToNode(this->getNodesContainerSize(), -1);
// De la bun inceput, stim ca distanta de la nodul sursa la el insusi este egala cu 0 (pentru ca nu trebuie parcursa nicio muchie). Prin urmare, vom actualiza
// distanta in vectorul de distante minime
minDistaceFromSourceToNode[sourceNode] = 0;
// Urmatorul pas al algoritmului lui Dikstra este sa mentinem o multime F de noduri pentru care distanta minima finala a fost deja calculata. Dupa pasii descrisi
// anterior, in aceasta multime vom avea doar nodul sursa, pentru ca doar pentru el avem deja calculata distanta minima finala (deci F = {sourceNode}).
// Pentru fiecare nod din multimea F (de la CEL MAI apropiat de sursa la cel mai indepartat), se cauta vecinii lui care nu sunt inclusi in F
//(deci pentru care nu s-a calculat inca distanta minima finala) si se realizeaza procesul denumit "relaxare".
// Relaxarea presupune ca, pentru fiecare vecin al nodului curent in parte, sa se verifice daca nu cumva putem obtine o distanta mai buna trecand prin
// nodul curent si mai apoi trecand de la nodul curent la vecin (stim ca avem muchie intre ele) decat distanta minima care exista deja pentru vecin.
// Daca acest lucru este adevarat, atunci actualizam distanta minima a vecinului la distanta minima a nodului curent + costul muchiei dintre nodul curent
// si vecin
// Dupa relaxare, si nodul vecin procesat va fi inclus in F, algoritmul garantand ca distanta minima finala a fost determinata si pentru el.
// Procedeul de relaxare a nodurilor si includerea acestora in multimea F se repeta pana cand in F sunt toate nodurile din graf. Cu alte cuvinte, atunci
// cand s-a calculat distanta minima finala pentru toate nodurile
// Determinarea celui mai apropiat vecin de un anumit nod este o operatie costisitoare, avand complexitate liniara in raport cu numarul de noduri
// Prin urmare, algoritmul lui Dijkstra ar avea o complexitate de timp de O(V^2) daca am folosi aceasta implementare, in care cautam un minim "brute-force".
// Putem imbunatati timpul de rulare al algoritmului prin a folosi o structura de date specializata in extractia/calcularea minimelor / maximelor peste o anumita multime,
//care sa ne ofere un timp mult mai bun pt obtinerea minimului / maximului.
// O astfel de structura de date este min/max heap-ul. In C++ putem implementa un min/max heap prin intermediul unui priority_queue peste un vector. Un priority queue este un adaptor
// de containere STL (adica o clasa care intern foloseste containerul respectiv), care practic ofera o interfata restrictionata asupra containerului astfel sa poata fi realizate doar
//un anumit set de operatii
// Pt ca un priority queue creeaza by default un max heap si noi vrem de fiecare data sa extragem vecinul de distanta minima al nodului curent, putem introduce in max heap
// perechi de forma (-cost, destinatie). In acest fel, max heap-ul va avea comportamentul unui min-heap, deoarece daca inmultim cu -1 o inegalitate intre doua costuri (care sunt numere pozitive),
// atunci si semnul inegalitaii se va schimba si implicit functia care compara intern elementele va returna rezultatul opus. Deci introducand costurile negative in heap, vom obtine comportamentul
// unui min heap
auto q = priority_queue<pair<double, int>>();
q.push({0, sourceNode});
while(!q.empty()) {
// Cat timp heap-ul nu este gol si inca mai avem muchii cu semnificatia (w, dest) = exista un drum de cost w de la nodul sursa la dest
// Extragem nodul cel mai apropiat de sursa pentru care inca nu s-a calculat distanta minima finala (deci nu se afla in multimea F)
auto nearestNode = q.top().second;
auto nearestNodeDistance = q.top().first;
q.pop();
// Trecem prin vecinii nodului nearestNode si realizam procedeul de relaxare a nodurilor
// In cazul in care se obtine o distanta mai buna trecand prin nearestNode (adica nodul curent), atunci introducem si vecinul (alaturi de noua distanta minima de la sursa) in heap. Aceasta
// insertie conditionala asigura faptul ca nodurile care sunt deja in multimea F (pt care s-a calculat deja distanta maxima finala) nu vor mai fi introduse din nou in heap.
for(int j = 0; j < adjList[nearestNode].size(); j++) {
// Verificam daca obtinem o distanta mai buna trecand prin nearestNode
// De asemenea, trebuie sa gestionam cazul in care distanta vecinului e -1
// Valorea nodului vecin cu nodul curent
int neighbor = adjList[nearestNode][j].first;
// Costul muchiei de la nodul curent la nodul vecin
double costOfEdgeFromCurrentToNeighbor = adjList[nearestNode][j].second;
if(minDistaceFromSourceToNode[neighbor] == -1 || minDistaceFromSourceToNode[neighbor] > minDistaceFromSourceToNode[nearestNode] + costOfEdgeFromCurrentToNeighbor) {
// Relaxarea nodului vecin
minDistaceFromSourceToNode[neighbor] = minDistaceFromSourceToNode[nearestNode] + costOfEdgeFromCurrentToNeighbor;
// Daca s-a obtinut o distanta mai buna, atunci atunci introducem si vecinul (alaturi de noua distanta minima de la sursa) in heap
q.push({minDistaceFromSourceToNode[neighbor], neighbor});
}
}
}
return NodeInfoContainer<double> {minDistaceFromSourceToNode};
}
NodeInfoContainer<int> DFS(int sourceNode, bool traverseAllConnectedComponents = true) {
// Functie ce implementeaza cautarea in adancime pe graf
// Cautarea in adancime presupune plecarea de un un anumit nod si apoi procesarea primului vecin al lui, dupa care procesarea primului vecin al primului vecin samd, parcurgand astfel graful in
// "adancime". Algoritmul este mult mai intuitiv vizual daca consideram cazul in care facem DFS pe un arbore din radacina. Practic arborele va fi parcurs in "adancime", formandu-se mai intai
// un lant / drum complet de la radacina catre o frunza, si mai apoi inca un lant complet de la o radacina la o frunza samd.
// Functia primeste si un parametru optinal denumit traverseAllConnectedComponents, care este true daca se doreste ca DFS-ul sa se faca pe toate componentele
// conexe ale grafului (in cazul in care graful este desigur neconex). In caz contrar (cand parametrul este setat la false), DFS-ul se va opri atunci cand
// se parcurg toate nodurile componentei conexe din care face parte sourceNode
// Complexitatea algoritmului este liniara in raport cu numarul de noduri, deoarece fiecare nod este parcurs o singura data. Pentru a ne asigura ca fiecare nod este vizitat o singura data, pastram
// un vector visited[i] = nodul i a fost vizitat sau nu
vector<int> nodesToStartDfsFrom;
nodesToStartDfsFrom.push_back(sourceNode);
// Daca se doreste traversarea tuturor componentelor conexe, atunci fiecare nod din graf reprezinta un punct potential de plecare pentru dfs
if(traverseAllConnectedComponents) {
for(int i = this->getFirstNodeIndex(); i <= this->getLastNodeIndex(); i++) {
if(i == sourceNode) {
continue;
}
nodesToStartDfsFrom.push_back(i);
}
}
// Avand in vedere natura recursiva a cautarii, aceasta poate fi implementata fie folosind o stiva, fie folosind capabilitatile de recursivitate oferite de limbajul de programare
auto dfsResult = vector<int>();
auto visited = vector<bool>(this->getNodesContainerSize(), false);
for(auto it: nodesToStartDfsFrom) {
if(!visited[it]) {
this->_DFSUtil(dfsResult, visited, it);
}
}
return NodeInfoContainer<int> {dfsResult};
}
// Functie ce returneaza numarul de componente conexe ale grafului
int getNumberOfConnectedComponents() {
// Implementarea se va face prin intermediul algoritmului de cautare in adancime. Se va retine intr-o variabila numarul de componente conexe, initial egal cu 0.
// Pt fiecare nod din graf, se verifica daca acesta este nevizitat si se apeleaza DFS pe el. Se incrementeaza numarul de componente conexe.
// Daca graful ar fi conex, atunci dupa apel nu ar mai trebui sa gasim niciun nod nevizitat. In schimb, daca mai sunt noduri nevizitate, atunci e clar ca
// graful nu este conex.
int connectedComponentsCount = 0;
auto dfsResult = vector<int>();
auto visited = vector<bool>(this->getNodesContainerSize(), false);
for(int i = this->getFirstNodeIndex(); i <= this->getLastNodeIndex(); i++) {
if(!visited[i]) {
++connectedComponentsCount;
this->_DFSUtil(dfsResult, visited, i);
}
}
return connectedComponentsCount;
}
bool isConnected() {
return this->getNumberOfConnectedComponents() == 1;
}
NodeInfoContainer<int> topologicalSort(bool traverseAllConnectedComponents = true) {
// Functie ce implementeaza sortarea topologica a nodurilor grafurilor.
// Daca exista muchia (x, y) in graf, spunem ca "x depinde de y". Sortarea topologica a nodurilor implica ordonarea nodurilor asa incat
// un nod X este pozitionat dupa toate nodurile de care depinde X
// Sortarea topologica este un caz particular ar parcurgerii in adancime, in sensul in care nodul este procesat de abia dupa ce toate nodurile
// de care depinde sunt procesate (in algoritmul clasic DFS, acesta este procesat inainte de apelul recursiv)
vector<int> nodesToStartDfsFrom;
nodesToStartDfsFrom.push_back(this->getFirstNodeIndex());
// Daca se doreste traversarea tuturor componentelor conexe, atunci fiecare nod din graf reprezinta un punct potential de plecare pentru dfs
if(traverseAllConnectedComponents) {
for(int i = this->getFirstNodeIndex(); i <= this->getLastNodeIndex(); i++) {
if(i == this->getFirstNodeIndex()) {
continue;
}
nodesToStartDfsFrom.push_back(i);
}
}
// Se va folosi tot rutina _DFSUtil cu parametrul postOrder = true, ceea ce ii spune functiei ca nodul curent trebuie sa fie procesat (in cazul nostru adaugat
//la rezultat) de abia dupa ce toti vecinii sunt procesati (vecinii = noduri care au o muchie interna de la nodul curent si deci de care nodul curent depinde)
int sourceNode = this->Opts.zeroIndexed ? 0 : 1;
auto dfsResult = vector<int>();
auto visited = vector<bool>(this->getNodesContainerSize(), false);
for(auto it: nodesToStartDfsFrom) {
if(!visited[it]) {
this->_DFSUtil(dfsResult, visited, it, true);
}
}
return NodeInfoContainer<int> {dfsResult};
}
NodeInfoContainer<int> BFS(int sourceNode) {
// Pentru parcurgerea in latime, se va folosi o coada in care se va introduce initial nodul sursa. Cat timp coada nu este goala, se extrage primul nod din coada si
// i se proceseaza vecinii nevizitati, adaugandu-se si ei in coada
auto bfsResult = vector<int>();
auto visited = vector<bool>(this->getNodesContainerSize(), false);
auto q = queue<int>();
q.push(sourceNode);
while(!q.empty()) {
int currentNode = q.front();
visited[currentNode] = true;
q.pop();
bfsResult.push_back(currentNode);
for(int j = 0; j < adjList[currentNode].size(); j++) {
int neighbor = adjList[currentNode][j].first;
if(!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
return NodeInfoContainer<int> {bfsResult};
}
friend ostream& operator<<(ostream& os, const Graph& G);
template <typename U>
friend ostream& operator<<(ostream& os, const Graph::NodeInfoContainer<U>& NodeInfo);
};
ostream& operator<<(ostream& os, const Graph& G) {
G.printAdjList();
return os;
}
template <typename U>
ostream& operator<<(ostream& os, const Graph::NodeInfoContainer<U>& NodeInfo) {
for(auto it: NodeInfo.nodeInfo) {
os << it << " ";
}
return os;
}
int main() {
auto G = new Graph(
Graph::GraphOpts {false, true, false, Graph::NodeSortOrder::ASCENDING_BY_NODE_KEY}
);
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int N, M, x, y;
fin >> N >> M;
for(int i = 0; i < M; i++) {
fin>> x >> y;
G->addEdge(y, x, 0);
}
fout << G->topologicalSort();
return 0;
}
Liviu Gheorghe liviu_gheorghe1234