#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
using namespace std;
const int INF = (1 << 30) - 1;
const int MAXXflow = 1001;
class Graph {
private:
int _n, _m;
bool _isOriented;
vector<vector<int>> _adjacentList;
vector<vector<pair<int, int> >> _adjacentListWithCosts;
vector<vector<pair<int, int> >> _adjacentListMultigraph;
public:
Graph(int nodes, int edges, bool oriented) : _n(nodes), _m(edges), _isOriented(oriented) {}
void addEdges(istream &f); // graf neorientat
void addEdgesOriented(istream &f); // graf orientat
void addEdgesWithCosts(ifstream &f); // graf neorientat cu costuri
void addEdgesOrientedWithCosts(ifstream &f); // graf orientat cu costuri
vector<int> bfs(int start);
int nrCompConexe();
vector<int> sortareTopologica();
vector<vector<int>> ctc();
vector<vector<int>> compBiconexe();
vector<int> Dijkstra(int s);
vector<pair<int, int>> apm(int node);
void Bellmanford(int s, ofstream &g);
void setAdjacentList(const vector<vector<int>> &adjacentList);
int maxFlow(vector<vector<int>> capacity);
int darb();
vector<pair<int, int>> cuplaj();
int hamilton();
void addEdgesMultigraph(ifstream &f);
vector<int> cicluEuler(int start);
private:
void dfs(int start, vector<int> &visited);
void dfsCtc(int node, vector<int> &visited, vector<int> &ordine);
void transpose();
void biconexe(int node, int parent, stack<int> &s, vector<int> &level, vector<int> &back, vector<vector<int>> &bic);
bool bfsFlow(int source, int destination, vector<vector<int>> capacity, vector<vector<int>> flow,
vector<int> &dad, queue<int> &q);
void dfsDarb(int start, vector<int> &level, int l, vector<int> &visited);
bool dfsCuplaj(int node, vector<int> &visited, vector<int> &left, vector<int> &right);
};
void Graph::addEdges(istream &f) {
int x, y;
_adjacentList.resize(_n + 1);
for (int i = 0; i < _m; ++i) {
f >> x >> y;
_adjacentList[x].push_back(y);
_adjacentList[y].push_back(x);
}
}
void Graph::addEdgesOriented(istream &f) {
int x, y;
_adjacentList.resize(_n + 1);
for (int i = 0; i < _m; ++i) {
f >> x >> y;
_adjacentList[x].push_back(y);
}
}
void Graph::addEdgesOrientedWithCosts(ifstream &f) {
int x, y, c;
_adjacentListWithCosts.resize(_n + 1);
for (int i = 0; i < _m; ++i) {
f >> x >> y >> c;
_adjacentListWithCosts[x].push_back(make_pair(y, c));
}
}
void Graph::addEdgesWithCosts(ifstream &f) {
int x, y, c;
_adjacentListWithCosts.resize(_n + 1);
for (int i = 0; i < _m; ++i) {
f >> x >> y >> c;
_adjacentListWithCosts[x].push_back(make_pair(y, c));
_adjacentListWithCosts[y].push_back(make_pair(x, c));
}
}
void Graph::addEdgesMultigraph(ifstream &f) {
int x, y;
_adjacentListMultigraph.resize(_n + 1);
for (int i = 1; i <= _m; ++i) {
f >> x >> y;
_adjacentListMultigraph[x].push_back(make_pair(y, i));
_adjacentListMultigraph[y].push_back(make_pair(x, i));
}
}
void Graph::setAdjacentList(const vector<vector<int>> &adjacentList) {
_adjacentList = adjacentList;
}
// parametri: nodul de start
// output: vector ce contine distanta din nodul sursa start la celelalte noduri
// Se insereaza nodul start intr-o coada vida, cu distanta 0. La fiecare pas, se ia nodul de la inceputul cozii,
// se elimina si apoi se adauga la finalul cozii vecinii la care nu s-a ajuns pana atunci.
// Distanta unui nod nou adaugat va fi distanta nodului care l-a adaugat + 1
/**
*
* @param start
* @return
*/
vector<int> Graph::bfs(int start) {
queue<int> q;
vector<int> dist(_n + 1);
for (int i = 1; i <= _n; i++) {
dist[i] = -1;
}
q.push(start);
dist[start] = 0;
while (!q.empty()) {
int node = q.front();
for (int i = 0; i < _adjacentList[node].size(); i++) {
if (dist[_adjacentList[node][i]] == -1) {
q.push(_adjacentList[node][i]);
dist[_adjacentList[node][i]] = dist[node] + 1;
}
}
q.pop();
}
return dist;
}
// parametri: nodul, vectorul de vizitari
void Graph::dfs(int node, vector<int> &visited) {
visited[node] = 1;
for (int i = 0; i < _adjacentList[node].size(); i++) {
if (!visited[_adjacentList[node][i]])
dfs(_adjacentList[node][i], visited);
}
}
// output: numarul componentelor conexe
int Graph::nrCompConexe() {
int i, nr = 0;
vector<int> visited(_n + 1, 0);
for (i = 1; i <= _n; i++) {
if (!visited[i]) {
nr++;
dfs(i, visited);
}
}
return nr;
}
// parametri: fisierul de intrare
// output: true daca se poate forma un graf cu secventa de grade data, false altfel
bool havel_hakimi(istream &f) {
vector<int> grade;
int x, s = 0;
//citesc gradele din fisier si calculez si suma
while (f >> x) {
grade.push_back(x);
s += x;
}
//verific sa nu fie un nod cu gradul mai mare de n-1
for (int i = 0; i < grade.size(); i++)
if (grade[i] > grade.size() - 1) {
return false;
}
//verific sa nu fie suma impara
if (s % 2) {
return false;
}
//sortez gradele descrescator
sort(grade.begin(), grade.end(), greater<int>());
//cat timp gradele nodurilor !=0, rulam algoritmul
while (grade[0] != 0) {
//scad cu 1 gradele urmatoarelor grad[0] noduri, apoi grad[0] devine 0
for (int i = 1; i <= grade[0]; i++) {
grade[i]--;
if (grade[i] < 0) {
return false;
}
}
grade[0] = 0;
sort(grade.begin(), grade.end(), greater<int>()); // la fiecare pas reordonam gradele descrescator
}
return true;
}
// output: vector ce contine sortarea topologica a nodurilor grafului dat
vector<int> Graph::sortareTopologica() {
vector<int> grade_interne(_n + 2, 0);
queue<int> coada;
vector<int> answer;
//calculez gradele interne ale nodurilor
for (int i = 1; i <= _n; i++)
for (int j = 0; j < _adjacentList[i].size(); j++)
grade_interne[_adjacentList[i][j]] += 1;
//adaug in coada toate nodurile cu gradul intern 0
for (int i = 1; i <= _n; i++)
if (grade_interne[i] == 0)
coada.push(i);
int varf;
while (!coada.empty()) {
//extragem un varf din coada
varf = coada.front();
answer.push_back(varf);
coada.pop();
//scad gradele interne ale vecinilor, fara sa elimin nodul din reprezentare si adaug in coada vecinii al caror
// grad intern devine 0
for (int i = 0; i < _adjacentList[varf].size(); i++) {
grade_interne[_adjacentList[varf][i]]--;
if (grade_interne[_adjacentList[varf][i]] == 0)
coada.push(_adjacentList[varf][i]);
}
}
return answer;
}
//graful transpus
void Graph::transpose() {
vector<int> transpEdges[_n + 1];
int i, j;
for (i = 1; i <= _n; i++)
for (j = 0; j < _adjacentList[i].size(); j++)
transpEdges[_adjacentList[i][j]].push_back(i);
for (i = 1; i <= _n; i++) {
_adjacentList[i] = transpEdges[i];
}
}
// parametri: nodul, vectorul de vizitari, vectorul de ordine
void Graph::dfsCtc(int node, vector<int> &visited, vector<int> &ordine) {
visited[node] = 1;
for (int i = 0; i < _adjacentList[node].size(); i++) {
if (!visited[_adjacentList[node][i]])
dfsCtc(_adjacentList[node][i], visited, ordine);
}
//in ordine pastrez nodurile cand sunt finalizate de dfs
ordine.push_back(node);
}
// output: matrice care contine pe fiecare linie o componentă tare conexă prin enumerarea nodurilor componente
vector<vector<int>> Graph::ctc() {
vector<vector<int>> ans;
vector<int> visited(_n + 1, 0);
vector<int> ordine;
for (int i = 1; i <= _n; i++) {
if (!visited[i]) {
dfsCtc(i, visited, ordine);
}
}
//inversez ordinea
reverse(ordine.begin(), ordine.end());
//fac graful transpus
transpose();
//resetez vectorul de vizitari
for (int i = 1; i <= _n; i++)
visited[i] = 0;
//fac dfs pentru elemente din ordine (cele inversate)
for (int i = 0; i < _n; i++) {
if (!visited[ordine[i]]) {
vector<int> v;
dfsCtc(ordine[i], visited, v);
ans.push_back(v);
}
}
return ans;
}
// parametri: nodul, parintele nodului, stiva, vector pentru nivelul fiecarui nod, vector pentru minimul de muchii
// prin care ne putem intoarce fara a trece prin parinte, matricea care contine pe fiecare linie cate o componenta biconexa
/**
*
* @param node
* @param parent
* @param s
* @param level
* @param back
* @param bic
*/
void
Graph::biconexe(int node, int parent, stack<int> &s, vector<int> &level, vector<int> &back, vector<vector<int>> &bic) {
//calculez nivelurile nodurilor
level[node] = level[parent] + 1;
back[node] = level[node];
s.push(node);
//parcurg vecinii
for (int i = 0; i < _adjacentList[node].size(); i++) {
if (level[_adjacentList[node][i]]) {
if (_adjacentList[node][i] != parent)
//actualizez minimul
back[node] = min(level[_adjacentList[node][i]], back[node]);
} else {
biconexe(_adjacentList[node][i], node, s, level, back, bic); //dfs pentru biconexe
back[node] = min(back[_adjacentList[node][i]], back[node]);
if (level[node] <= back[_adjacentList[node][i]]) { //verific daca face parte din componenta biconexa
vector<int> v;
while (s.top() != _adjacentList[node][i]) {
v.push_back(s.top()); //pun in v elementele componentei biconexe
s.pop();
}
v.push_back(_adjacentList[node][i]);
s.pop();
v.push_back(node);
bic.push_back(v);
}
}
}
}
// output: matrice care contine pe fiecare linie cate o componenta biconexa
vector<vector<int>> Graph::compBiconexe() {
vector<vector<int>> bic;
//initializez cu 0 vectorii pentru nivel si pentru intoarcere
vector<int> level(_n + 1, 0);
vector<int> back(_n + 1, 0);
stack<int> s;
for (int i = 1; i <= _n; i++) {
//pentru fiecare nod, in functia biconexe incep sa calculez nivelul daca acesta nu este inca setat
if (!level[i]) {
biconexe(i, 0, s, level, back, bic);
//golesc stiva
while (!s.empty()) {
s.pop();
}
}
}
return bic;
}
// parametri: nodul de start
// output: vector cu n-1 numere naturale separate printr-un spatiu. Al i-lea numar va reprezenta lungimea unui
// drum minim de la nodul start la nodul i+1
vector<int> Graph::Dijkstra(int start) {
vector<int> dist(_n + 1, INF);
vector<int> visited(_n + 1, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
dist[start] = 0;
q.push(make_pair(0, start));
while (!q.empty()) {
int currentNode = q.top().second; //extrag varful cu eticheta minima din q
q.pop();
if (visited[currentNode] == 0) {
visited[currentNode] = 1;
for (int i = 0; i < _adjacentListWithCosts[currentNode].size(); ++i) {
int neighbour = _adjacentListWithCosts[currentNode][i].first;
int cost = _adjacentListWithCosts[currentNode][i].second;
if (dist[neighbour] > dist[currentNode] + cost) { // actualizez drumul cand gasesc un cost mai mic
dist[neighbour] = dist[currentNode] + cost;
q.push(make_pair(dist[neighbour], neighbour));
}
}
}
}
return dist;
}
// parametri: nodul de start
// output: vector de pair care contine muchiile ce apartin arborelui solutie
vector<pair<int, int>> Graph::apm(int start) {
vector<pair<int, int>> answer;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
vector<int> costs(_n + 1, INF);
vector<int> dad(_n + 1, 0);
vector<int> visited(_n + 1, 0);
int total = 0;
dad[start] = 0;
costs[start] = 0;
q.push(make_pair(0, start));
while (!q.empty()) {
int currentNode = q.top().second;
q.pop();
if (visited[currentNode] == 0) {
visited[currentNode] = 1;
for (int i = 0; i < _adjacentListWithCosts[currentNode].size(); ++i) {
int neighbour = _adjacentListWithCosts[currentNode][i].first;
int cost = _adjacentListWithCosts[currentNode][i].second;
if (visited[neighbour] == 0 &&
cost < costs[neighbour]) { // actualizez cand gasesc un cost mai mic la un vecin nevizitat
costs[neighbour] = cost;
dad[neighbour] = currentNode;
q.push(make_pair(costs[neighbour], neighbour));
}
}
total += costs[currentNode];
if (dad[currentNode] != 0)
answer.push_back(make_pair(currentNode, dad[currentNode]));
}
}
return answer;
}
// parametri: nodul x, vectorul de tati
// output: radacina nodului
int Find(int x, vector<int> &dad) {
int root, aux;
root = x;
while (root != dad[root])
root = dad[root];
while (x != dad[x]) {
aux = dad[x];
dad[x] = root;
x = aux;
}
return root;
}
// parametri: nodul x, nodul y, vectorul de tati, vectorul de ranguri
// output: realizeaza reuniunea dintre multimile in care se afla elementul x, respectiv elementul y
void Union(int x, int y, vector<int> &dad, vector<int> &rang) {
int root_x = Find(x, dad);
int root_y = Find(y, dad);
if (rang[root_x] > rang[root_y]) {
dad[root_y] = root_x;
rang[root_x] += rang[root_y];
} else {
dad[root_x] = root_y;
rang[root_y] += rang[root_x];
}
}
// parametri: nodul de start, fisierul in care se scrie rezultatul
// output: in fisier este scris costul minim al unui lanţ de la nodul start la celelalte noduri sau "ciclu negativ" daca apare
void Graph::Bellmanford(int start, ofstream &g) {
vector<int> dist(_n + 1, INF);
queue<int> q; // optimizare folosind coada
vector<int> inQueue(_n + 1, 0);
vector<int> visited(_n + 1, 0);
dist[start] = 0;
q.push(start);
inQueue[start] = 1;
while (!q.empty()) {
int currentNode = q.front();
q.pop();
visited[currentNode] += 1; // numar de cate ori a fost vizitat un nod pentru a detecta ciclurile
inQueue[currentNode] = 0;
if (visited[currentNode] >= _n) {
g << "Ciclu negativ!";
return;
}
for (int i = 0; i < _adjacentListWithCosts[currentNode].size(); ++i) {
int neighbour = _adjacentListWithCosts[currentNode][i].first;
int cost = _adjacentListWithCosts[currentNode][i].second;
if (dist[neighbour] > dist[currentNode] + cost) { // actualizez cand gasesc un cost mai mic
dist[neighbour] = dist[currentNode] + cost;
if (inQueue[neighbour] == 0) {
q.push(neighbour);
inQueue[neighbour] = 1;
}
}
}
}
for (int i = 2; i <= _n; ++i)
g << dist[i] << " ";
}
// Edmonds-Karp
// parametri: nodul sursa, nodul destinatie, matricea pentru capacitati, matricea pentru flow, vector de tati, coada
// output: true daca s-a ajuns la destinatie, false altfel
bool Graph::bfsFlow(int source, int destination, vector<vector<int>> capacity, vector<vector<int>> flow,
vector<int> &dad, queue<int> &q) {
for (int i = 1; i <= _n; i++) {
dad[i] = 0;
}
q.push(source);
dad[source] = source;
int arrivedAtDestination = 0;
while (!q.empty()) {
int currentNode = q.front();
q.pop();
if (currentNode == destination) {
arrivedAtDestination = 1;
continue;
}
for (auto &node: _adjacentList[currentNode]) {
if ((capacity[currentNode][node] - flow[currentNode][node] > 0) && dad[node] == 0) {
dad[node] = currentNode;
q.push(node);
}
}
}
return arrivedAtDestination;
}
// parametri: matrice pentru capacitati
// output: capacitatea maxima
int Graph::maxFlow(vector<vector<int>> capacity) {
int source = 1, destination = _n;
vector<vector<int>> flow(MAXXflow, vector<int>(MAXXflow, 0));
vector<int> dad(_n + 1, 0);
queue<int> q;
int answer = 0;
while (bfsFlow(source, destination, capacity, flow, dad, q)) { // cat timp exista drumuri
for (auto &node: _adjacentList[destination]) {
int currentNode = destination;
int minim = INF;
if (dad[node] == 0) { // daca nu se ajunge la acel nod, se trece mai departe
continue;
}
dad[destination] = node;
while (currentNode != source) {
minim = min(minim, capacity[dad[currentNode]][currentNode] - flow[dad[currentNode]][currentNode]);
currentNode = dad[currentNode];
}
currentNode = destination;
while (currentNode != source) {
flow[dad[currentNode]][currentNode] += minim;
flow[currentNode][dad[currentNode]] -= minim;
currentNode = dad[currentNode];
}
answer += minim;
}
}
return answer;
}
// parametri: nodul, vector pentru nivel, vector de vizitari
void Graph::dfsDarb(int node, vector<int> &level, int l, vector<int> &visited) {
visited[node] = 1;
level[node] = l;
for (int i = 0; i < _adjacentList[node].size(); ++i) {
if (!visited[_adjacentList[node][i]]) {
dfsDarb(_adjacentList[node][i], level, l + 1, visited);
}
}
}
// output: diametrul arborelui
int Graph::darb() {
int diameter = 0;
vector<int> level(_n + 1, 0);
vector<int> visited(_n + 1, 0);
int maxLevel = 0;
int finale = 0;
dfsDarb(1, level, 1, visited);
for (int i = 0; i < _n; ++i)
if (level[i] > maxLevel) {
maxLevel = level[i];
finale = i;
}
for (int i = 0; i <= _n; ++i) {
visited[i] = 0;
}
level.clear();
dfsDarb(finale, level, 1, visited);
for (int i = 0; i <= _n; ++i)
if (level[i] > diameter)
diameter = level[i];
return diameter;
}
// parametri: numarul de noduri, matricea in care se construiesc drumurile minime
// output: se formeaza matricea drumurilor minime
void royfloyd(int n, int matrix[105][105]) {
for (int k = 1; k <= n; ++k) {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (matrix[i][j] > matrix[i][k] + matrix[k][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
// parametri: nodul, vectorul de vizitari, perechile nodurilor din stanga, perechile nodurilor din dreapta
// output: true, daca s-a format pereche sau lant alternant, si false altfel
// DFS-ul acesta va cauta nodurile din prima multime care inca nu au pereche si o va forma
// sau nodurile care au pereche din prima multime, dar continua cu lant alternant care accepta o augmentare de o unitate de flux
// Functia returneaza true, daca s-a format pereche sau lant alternant, si false altfel.
// Hopcroft-Karp
bool Graph::dfsCuplaj(int node, vector<int> &visited, vector<int> &left, vector<int> &right) {
if (visited[node])
return false;
visited[node] = 1;
for (int i = 0; i < _adjacentList[node].size(); ++i)
if (!right[_adjacentList[node][i]] || dfsCuplaj(right[_adjacentList[node][i]], visited, left, right)) {
right[_adjacentList[node][i]] = node;
left[node] = _adjacentList[node][i];
return true;
}
return false;
}
// output: vector de pair care reprezinta cuplajul
vector<pair<int, int>> Graph::cuplaj() {
vector<pair<int, int>> answer;
vector<int> left(10001, 0), right(10001, 0);
vector<int> visited(_n + 1, 0);
bool ok;
do {
ok = false;
for (int i = 0; i <= _n; ++i)
visited[i] = 0;
for (int i = 1; i <= _n; ++i)
if (left[i] == 0 && dfsCuplaj(i, visited, left, right))
ok = true;
} while (ok == true);
for (int i = 1; i <= _n; ++i)
if (left[i] != 0)
answer.push_back(make_pair(i, left[i]));
return answer;
}
// output: costul minim al nodurilor care ajung in nodul 0
// Se creeaza matricea costurilor a tuturor drumurilor, care initial e initializata cu INF.
// Se foloseste reprezentarea binara pentru a retine nodurile care fac parte din lant (de la 0 la j), acestea fiind marcate cu 1
// Pentru fiecare lant, se verifica nodurile care fac parte din acesta. Se parcurge lista de adiacenta a lui j si se verifica
// daca se obtine un cost mai bun cu ajutorul unui vecin, apoi actualizez costul
// La final este cautat costul minim al nodurilor care ajung in nodul 0, deoarece cu acesta am inceput, plus costul muchiei
// de la nod la 0
int Graph::hamilton() {
int answer = INF;
int nodes = 1 << _n; //2^n
int cost[nodes][_n];
for (int i = 0; i < nodes; ++i)
for (int j = 0; j < _n; ++j)
cost[i][j] = INF;
cost[1][0] = 0; // bitul 0 este 1, 2^0=1; fixez nodul de inceput 0, care are costul 0
for (int i = 0; i < nodes; ++i)
for (int j = 0; j < _n; ++j)
if ((i & (1 << j))) { // verific nodurile care fac parte din lant
for (int k = 0; k < _adjacentListWithCosts[j].size(); ++k) {
if (i & (1 << _adjacentListWithCosts[j][k].first)) { // verific ca vecinul sa faca parte din lant
cost[i][j] = min(cost[i][j], cost[i ^ (1 << j)][_adjacentListWithCosts[j][k].first] +
_adjacentListWithCosts[j][k].second); // nu se poate merge print-un nod
// de mai multe ori, deci eliminam nodul j cand compar costurile
}
}
}
for (int i = 0; i < _adjacentListWithCosts[0].size(); ++i)
answer = min(answer, cost[nodes - 1][_adjacentListWithCosts[0][i].first] +
_adjacentListWithCosts[0][i].second);
return answer;
}
// parametri: nodul de start
// output: vector ce contine ciclul eulerian
// Se verifica intai daca toate nodurile au gradele pare.
// La inceput se pune intr-o stiva nodul de start.
// Cat timp stiva nu este vida, se ia nodul curent, apoi ultimul vecin al acestuia din lista,
// pentru a fi usor de sters muchia.
// Se sterge muchia cu pop_back(), apoi se viziteaza muchia si se adauga in stiva nodul la care a dus muchia.
// Daca nodul nu mai are vecini, atunci este scos din stiva si adaugat la ciclul eulerian.
vector<int> Graph::cicluEuler(int start) {
vector<int> answer;
vector<int> visitedEdges(_m + 1, 0);
for (int i = 0; i < _n; ++i)
if (_adjacentListMultigraph[i].size() % 2 != 0) {
answer.push_back(-1);
return answer;
}
stack<int> euler;
euler.push(start);
while (!euler.empty()) {
int currentNode = euler.top();
if (_adjacentListMultigraph[currentNode].size() != 0) {
int neighbour = _adjacentListMultigraph[currentNode].back().first;
int index = _adjacentListMultigraph[currentNode].back().second;
_adjacentListMultigraph[currentNode].pop_back();
if (visitedEdges[index] == 0) {
visitedEdges[index] = 1;
euler.push(neighbour);
}
} else {
euler.pop();
answer.push_back(currentNode);
}
}
return answer;
}
void solve_bfs() {
ifstream f("bfs.in");
ofstream g("bfs.out");
int n, m, s;
f >> n >> m >> s;
Graph gr(n, m, true);
gr.addEdgesOriented(f);
vector<int> answer = gr.bfs(s);
for (int i = 1; i <= n; ++i) {
g << answer[i] << " ";
}
f.close();
g.close();
}
void solve_nrCompConexe() {
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m;
f >> n >> m;
Graph gr(n, m, false);
gr.addEdges(f);
g << gr.nrCompConexe();
f.close();
g.close();
}
void solve_sortareTopologica() {
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n, m;
f >> n >> m;
Graph gr(n, m, true);
gr.addEdgesOriented(f);
vector<int> answer = gr.sortareTopologica();
for (int i = 0; i < answer.size(); ++i)
g << answer[i] << ' ';
f.close();
g.close();
}
void solve_ctc() {
ifstream f("ctc.in");
ofstream g("ctc.out");
int n, m;
f >> n >> m;
Graph gr(n, m, true);
gr.addEdgesOriented(f);
vector<vector<int>> answer = gr.ctc();
g << answer.size() << '\n';
for (int i = 0; i < answer.size(); i++) {
for (int j = 0; j < answer[i].size(); j++)
g << answer[i][j] << " ";
g << '\n';
}
}
void solve_biconex() {
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
f >> n >> m;
Graph gr(n, m, false);
gr.addEdges(f);
vector<vector<int>> answer = gr.compBiconexe();
g << answer.size() << '\n';
for (int i = 0; i < answer.size(); i++) {
for (int j = 0; j < answer[i].size(); j++)
g << answer[i][j] << " ";
g << '\n';
}
f.close();
g.close();
}
void solve_Dijkstra() {
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m;
f >> n >> m;
Graph gr(n, m, true);
gr.addEdgesOrientedWithCosts(f);
vector<int> answer = gr.Dijkstra(1);
for (int i = 2; i <= n; ++i)
if (answer[i] != INF)
g << answer[i] << ' ';
else g << 0 << ' ';
}
void solve_HavelHakimi() {
ifstream f("hh.in");
ofstream g("hh.out");
bool answer = havel_hakimi(f);
if (answer) g << "Da.\n";
else g << "Nu.\n";
f.close();
}
void solve_apm() {
ifstream f("apm.in");
ofstream g("apm.out");
int n, m;
f >> n >> m;
Graph gr(n, m, false);
gr.addEdgesWithCosts(f);
vector<pair<int, int>> answer = gr.apm(1);
g << answer.size() << '\n';
for (int i = 0; i < answer.size(); ++i) {
g << answer[i].first << " " << answer[i].second << '\n';
}
f.close();
g.close();
}
void solve_disjoint() {
ifstream f("disjoint.in");
ofstream g("disjoint.out");
int n, m, cod, x, y;
f >> n >> m;
vector<int> dad(n + 1);
vector<int> rang(n + 1, 0);
for (int i = 1; i <= n; ++i) {
dad[i] = i;
}
for (int i = 0; i < m; ++i) {
f >> cod >> x >> y;
if (cod == 1) Union(x, y, dad, rang);
else {
if (Find(x, dad) == Find(y, dad))
g << "DA\n";
else g << "NU\n";
}
}
f.close();
g.close();
}
void solve_bellmanford() {
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n, m;
f >> n >> m;
Graph gr(n, m, false);
gr.addEdgesOrientedWithCosts(f);
gr.Bellmanford(1, g);
f.close();
g.close();
}
void solve_maxFlow() {
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int n, m, answer, x, y, z;
f >> n >> m;
Graph grf(n, m, false);
vector<vector<int>> gr(100001);
vector<vector<int>> capacity(MAXXflow, vector<int>(MAXXflow, 0));
for (int i = 0; i < m; ++i) {
f >> x >> y >> z;
gr[x].push_back(y);
gr[y].push_back(x);
capacity[x][y] = z;
}
grf.setAdjacentList(gr);
answer = grf.maxFlow(capacity);
g << answer;
f.close();
g.close();
}
void solve_darb() {
ifstream f("darb.in");
ofstream g("darb.out");
int n, x, y;
f >> n;
Graph gr(n, n - 1, false);
gr.addEdges(f);
g << gr.darb();
f.close();
g.close();
}
void solve_royfloyd() {
ifstream f("royfloyd.in");
ofstream g("royfloyd.out");
int n;
int matrix[105][105];
f >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
f >> matrix[i][j];
if (matrix[i][j] == 0 && i != j)
matrix[i][j] = 1001;
}
}
royfloyd(n, matrix);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
if (matrix[i][j] == 1001)
g << 0 << " ";
else
g << matrix[i][j] << " ";
g << '\n';
}
f.close();
g.close();
}
void solve_cicluEuler() {
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n, m;
f >> n >> m;
Graph gr(n, m, false);
gr.addEdgesMultigraph(f);
vector<int> answer = gr.cicluEuler(1);
if (answer[0] == -1) {
g << -1;
} else {
for (int i = 0; i < answer.size() - 1; ++i) {
g << answer[i] << " ";
}
}
f.close();
g.close();
}
void solve_hamilton() {
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n, m;
f >> n >> m;
Graph gr(n, m, true);
gr.addEdgesOrientedWithCosts(f);
int answer = gr.hamilton();
if (answer == INF)
g << "Nu exista solutie";
else
g << answer;
f.close();
g.close();
}
void solve_cuplaj() {
ifstream f("cuplaj.in");
ofstream g("cuplaj.out");
int n, m, e, x, y;
f >> n >> m >> e;
Graph gr(n, e, true);
gr.addEdgesOriented(f);
vector<pair<int, int>> answer = gr.cuplaj();
g << answer.size() << '\n';
for (int i = 0; i < answer.size(); ++i)
g << answer[i].first << " " << answer[i].second << '\n';
f.close();
g.close();
}
int main() {
// solve_HavelHakimi();
// solve_royfloyd();
// solve_disjoint();
// solve_cicluEuler();
// solve_Dijkstra();
// solve_apm();
// solve_bellmanford();
// solve_hamilton();
// solve_bfs();
// solve_nrCompConexe();
solve_sortareTopologica();
// solve_biconex();
// solve_ctc();
// solve_cuplaj();
// solve_darb();
// solve_maxFlow();
return 0;
}