#include <bits/stdc++.h>
using namespace std;
ifstream f;
ofstream g;
class Graf {
int noduri, muchii;
vector< vector<int> > lista;
public:
Graf(int numar_noduri, int numar_muchii, int aux);
Graf(int numar_noduri, int numar_muchii);
Graf(int numar_noduri);
Graf(int numar_noduri, int numar_muchii, string apm);
Graf();
void out();
void bfs(int start);
void dfs(vector<bool> &vizitat, int start);
void biconex();
void dfs_biconex(int start, vector<bool> &vizitat, int niv, vector<int> &nivel, vector<int> &nivel_intoarcere, vector<int> &parinte, vector < pair <int, int> > &st, int &contor, vector<set<int>> &componeneteBiconexe);
void componenteTareConexe(int nod, vector<int> &rezultat, vector <int> &nivel, vector <int> &nivelMinim, vector <bool> &stiva, stack <int> &st, vector < vector <int> > &output, int adancime);
void sortaret(int start, vector<bool> &vizitat, vector<int> &output);
bool Havel_Hakimi(int n, vector<int> &grade);
void critical();
void dfs_critical(int nod, int nodAnterior, vector<int> &nivel, vector<int> &nivelMinim, vector< vector <int> > &output, int adancime);
void apm();
int apm_parinte(int parinte[], int nod);
void disjoint();
void uniune(vector<int> &parinte, vector<int> &rang, int x, int y);
int cauta(vector<int> &parinte, int x);
void dijkstra();
};
Graf :: Graf()
{
noduri = 0;
muchii = 0;
lista.resize(0);
}
void Graf :: out ()
{
g << noduri << " " << muchii << endl;
for(int i = 0; i < noduri + 1; i++)
{
g << i << " : ";
for(int j = 0 ; j < lista[i].size(); j++)
g << lista[i][j] << " ";
g << endl;
}
}
Graf :: Graf (int numar_noduri, int numar_muchii, int aux)
{
noduri = numar_noduri;
muchii = numar_muchii;
int nod_1, nod_2;
lista.resize(numar_noduri + 1);
for(int i = 1; i <= numar_muchii; i++)
{
f >> nod_1 >> nod_2;
lista[nod_1].push_back(nod_2);
}
}
Graf :: Graf (int numar_noduri, int numar_muchii)
{
noduri = numar_noduri;
muchii = numar_muchii;
int nod_1, nod_2;
lista.resize(numar_noduri + 1);
for(int i = 1; i <= numar_muchii; i++)
{
f >> nod_1 >> nod_2;
lista[nod_1].push_back(nod_2);
lista[nod_2].push_back(nod_1);
}
}
Graf :: Graf (int numar_noduri)
{
noduri = numar_noduri;
int nod_1, nod_2;
lista.resize(numar_noduri + 1);
while(f >> nod_1 >> nod_2)
{
lista[nod_1].push_back(nod_2);
lista[nod_2].push_back(nod_1);
}
}
void Graf :: bfs(int start)
{
int distanta[noduri + 1];
for(int index = 1; index <= noduri; index++)
distanta[index] = -1;
bool vizitat[noduri + 1] = {false};
queue<int> q;
q.push(start);
distanta[start] = 0;
vizitat[start] = true;
while(!q.empty())
{
int nod = q.front();
q.pop();
for(int index = 0; index < lista[nod].size(); index++)
if(vizitat[lista[nod][index]] == false)
{
q.push(lista[nod][index]);
vizitat[lista[nod][index]] = true;
distanta[lista[nod][index]] = distanta[nod] + 1;
}
}
for(int secondIndex = 1; secondIndex <= noduri; secondIndex++)
g << distanta[secondIndex] << " ";
}
void Graf :: dfs(vector<bool> &vizitat, int start)
{
vizitat[start] = true;
for(int index = 0; index < lista[start].size(); index++)
if(vizitat[lista[start][index]] == false)
dfs(vizitat, lista[start][index]);
}
void Graf :: biconex()
{
int contor = 0;
vector<bool> vizitat;
vizitat.resize(noduri + 1);
vector<int> nivel;
vector<int> nivel_intoarcere;
vector<int> parinte;
vector< set <int> > componenteBiconexe;
nivel.resize(noduri + 1);
nivel_intoarcere.resize(noduri + 1);
parinte.resize(noduri + 1);
vector < pair<int, int>> st;
for(int index = 1; index <= noduri; index++)
{
nivel[index] = 0;
nivel_intoarcere[index] = 0;
vizitat[index] = false;
}
for(int index = 1; index <= noduri; index++)
{
if(vizitat[index] == false)
{
dfs_biconex(index, vizitat, 1, nivel, nivel_intoarcere, parinte, st, contor, componenteBiconexe);
int j = 0;
set<int> set_aux;
while(!st.empty())
{
j = 1;
set_aux.insert(st.back().first);
set_aux.insert(st.back().second);
st.pop_back();
}
componenteBiconexe.push_back(set_aux);
if(j == 1)
{
contor++;
}
}
}
g << contor << endl;
for(int index = 0; index < componenteBiconexe.size(); index++)
{
set<int>::iterator it;
for(it = componenteBiconexe[index].begin(); it != componenteBiconexe[index].end(); it++)
g << *it << " ";
g << endl;
}
}
void Graf :: dfs_biconex(int start, vector<bool> &vizitat, int niv, vector<int> &nivel, vector<int> &nivel_intoarcere, vector<int> &parinte, vector < pair < int, int> > &st, int &contor, vector<set<int>> &componenteBiconexe)
{
vizitat[start] = true;
nivel[start] = nivel_intoarcere[start] = niv;
int copil = 0;
for(int index = 0; index < lista[start].size(); index++)
{
int nod = lista[start][index];
if(vizitat[nod] == false)
{
copil++;
parinte[nod] = start;
pair<int, int> aux;
aux.first = start;
aux.second = nod;
st.push_back(aux);
dfs_biconex(nod, vizitat, niv + 1, nivel, nivel_intoarcere, parinte, st, contor, componenteBiconexe);
nivel_intoarcere[start] = min(nivel_intoarcere[start], nivel_intoarcere[nod]);
if( (nivel[start] == 1 && copil > 1) || (nivel[start] > 1 && nivel_intoarcere[nod] >= nivel[start]) )
{
set<int> set_aux;
while(st.back().first != start || st.back().second != nod)
{
set_aux.insert(st.back().first);
set_aux.insert(st.back().second);
st.pop_back();
}
set_aux.insert(st.back().first);
set_aux.insert(st.back().second);
componenteBiconexe.push_back(set_aux);
st.pop_back();
contor++;
}
}
else if(nod != parinte[start])
{
nivel_intoarcere[start] = min(nivel_intoarcere[start], nivel[nod]);
if(nivel[nod] < nivel[start])
{
pair<int, int> aux;
aux.first = start;
aux.second = nod;
st.push_back(aux);
}
}
}
}
void Graf :: componenteTareConexe(int nod, vector<int> &rezultat, vector <int> &nivel, vector <int> &nivelMinim, vector <bool> &stiva, stack <int> &st, vector < vector <int> > &output, int adancime)
{
nivel[nod] = adancime;
nivelMinim[nod] = adancime;
st.push(nod);
stiva[nod] = true;
for(int index = 0; index < lista[nod].size(); index++)
{
if(nivel[lista[nod][index]] == -1)
{
componenteTareConexe(lista[nod][index], rezultat, nivel, nivelMinim, stiva, st, output, adancime + 1);
nivelMinim[nod] = min(nivelMinim[nod], nivelMinim[lista[nod][index]]);
}
else if(stiva[lista[nod][index]])
nivelMinim[nod] = min(nivelMinim[nod], nivelMinim[lista[nod][index]]);
}
if(nivel[nod] == nivelMinim[nod])
{
rezultat.clear();
int node;
do
{
rezultat.push_back(node = st.top());
st.pop();
stiva[node] = false;
}
while(node != nod);
output.push_back(rezultat);
}
}
void Graf :: sortaret(int start, vector<bool> &vizitat, vector<int> &output)
{
vizitat[start] = true;
for(int index = 0; index < lista[start].size(); index++)
if(vizitat[lista[start][index]] == false)
sortaret(lista[start][index], vizitat, output);
output.push_back(start);
}
bool Graf :: Havel_Hakimi(int n, vector<int> &grade)
{
while(true)
{
sort(grade.begin(), grade.end(), greater<>());
if(grade[0] == 0)
return true;
int nod = grade[0];
grade.erase(grade.begin() + 0);
if(nod > grade.size())
return false;
for(int index = 0; index < nod; index++)
{
grade[index]--;
if(grade[index] < 0)
return false;
}
}
}
void Graf :: critical()
{
vector<int> nivel;
vector<int> nivelMinim;
vector< vector <int> > output;
nivel.resize(noduri);
nivelMinim.resize(noduri);
int adancime = 1;
dfs_critical(0, -1, nivel, nivelMinim, output, adancime);
for(int index = 0; index < output.size(); index++)
{
for(int secondIndex = 0; secondIndex < output[index].size(); secondIndex++)
g << output[index][secondIndex] << " ";
g << endl;
}
}
void Graf :: dfs_critical(int nod, int nodAnterior, vector<int> &nivel, vector<int> &nivelMinim, vector< vector <int> > &output, int adancime)
{
nivel[nod] = nivelMinim[nod] = adancime;
for(int index = 0; index < lista[nod].size(); index++)
{
int nodUrmator = lista[nod][index];
if (nivel[nodUrmator] == 0)
{
dfs_critical(nodUrmator, nod, nivel, nivelMinim, output, adancime + 1);
nivelMinim[nod] = min(nivelMinim[nod], nivelMinim[nodUrmator]);
}
else
if (nodUrmator != nodAnterior)
nivelMinim[nod] = min(nivelMinim[nod], nivel[nodUrmator]);
if (nivelMinim[nodUrmator] > nivel[nod])
output.push_back({nod, nodUrmator});
}
}
void Graf :: apm()
{
int rezultat = 0, cost, x, y, parinte[noduri + 1], rang[noduri + 1], numar_muchii = 0; // parinte[i] - parintele lui i | rang[i] - rangul lui i (inaltime)
f >> noduri >> muchii;
vector<pair<int, pair<int, int>>> edges;
vector<pair<int, int>> rez;
edges.resize(noduri + 1);
for(int index = 0; index < noduri + 1; index++)
{
parinte[index] = 0;
rang[index] = 1;
}
for(int index = 0; index < muchii; index++)
{
f >> x >> y >> cost;
edges.push_back(make_pair(cost, make_pair(x, y)));
}
sort(edges.begin(), edges.end());
for(int index = 0; index < edges.size() && numar_muchii != noduri - 1; index++)
{
x = edges[index].second.first;
y = edges[index].second.second;
cost = edges[index].first;
int parinte_x = apm_parinte(parinte, x);
int parinte_y = apm_parinte(parinte, y);
int aux;
if(parinte_x != parinte_y)
{
numar_muchii++;
rez.push_back(make_pair(x, y));
rezultat += cost;
int rang_x = rang[parinte_x], rang_y = rang[parinte_y];
if(rang_x < rang_y)
{
parinte[parinte_x] = parinte_y;
rang[parinte_y] = max(rang_y, rang_x + 1);
}
else
{
parinte[parinte_y] = parinte_x;
rang[parinte_x] = max(parinte_x, parinte_y + 1);
}
}
while(x != parinte_x)
{
aux = parinte[x];
parinte[x] = parinte_x;
x = aux;
}
while(y != parinte_y)
{
aux = parinte[y];
parinte[y] = parinte_y;
y = aux;
}
}
g << rezultat << endl << noduri - 1 << endl;
for(int index = 0; index < rez.size(); index++)
g << rez[index].first << " " << rez[index].second << endl;
}
int Graf :: apm_parinte(int parinte[], int nod)
{
if(parinte[nod] == 0)
return nod;
apm_parinte(parinte, parinte[nod]);
}
void Graf :: disjoint()
{
int numar_noduri, numar_comenzi, op, x, y;
f >> numar_noduri >> numar_comenzi;
vector<int> rang;
vector<int> parinte;
rang.resize(numar_noduri + 1);
parinte.resize(numar_noduri + 1);
for(int index = 0; index < numar_noduri + 1; index++)
{
parinte[index] = index;
rang[index] = 0;
}
for(int index = 0; index < numar_comenzi; index++)
{
f >> op >> x >> y;
if(op == 1)
{
uniune(parinte, rang, x, y);
}
else if(op == 2)
{
if(cauta(parinte, x) == cauta(parinte, y) )
g << "DA\n";
else
g << "NU\n";
}
}
}
void Graf :: uniune(vector<int> &parinte, vector<int> &rang, int x, int y)
{
int xset = cauta(parinte, x);
int yset = cauta(parinte, y);
if(xset == yset)
return;
if(rang[xset] < rang[yset])
parinte[xset] = yset;
else if(rang[xset] > rang[yset])
parinte[yset] = xset;
else
{
parinte[yset] = xset;
rang[xset] = rang[xset] + 1;
}
}
int Graf :: cauta(vector<int> &parinte, int x)
{
if(parinte[x] != x)
parinte[x] = cauta(parinte, parinte[x]);
return parinte[x];
}
void Graf :: dijkstra()
{
int x, y, cost;
f >> noduri >> muchii;
vector<vector<pair<int, int>>> edges;
vector<int> distanta;
vector<bool> ales;
edges.resize(noduri + 1);
distanta.resize(noduri + 1);
ales.resize(noduri + 1);
for(int index = 0; index < muchii; index++)
{
f >> x >> y >> cost;
edges[x].push_back(make_pair(y, cost));
}
for(int index = 0; index < noduri + 1; index++)
{
distanta[index] = INT_MAX;
ales[index] = false;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
distanta[1] = 0;
pq.push(make_pair(0, 1));
while(!pq.empty())
{
int nod = pq.top().second;
pq.pop();
if(ales[nod])
continue;
ales[nod] = true;
for(int index = 0; index < edges[nod].size(); index++)
{
int nod_2 = edges[nod][index].first;
cost = edges[nod][index].second;
if(distanta[nod_2] > distanta[nod] + cost)
{
distanta[nod_2] = distanta[nod] + cost;
pq.push(make_pair(distanta[nod_2], nod_2));
}
}
}
for(int index = 2; index < noduri + 1; index++)
if(distanta[index] != INT_MAX)
g << distanta[index] << " ";
}
int main()
{
int problema = 10;
if(problema == 1) // 100
{
f.open ("bfs.in", std::ifstream::in);
g.open ("bfs.out", std::ifstream::out);
int n, m, s;
f >> n >> m >> s;
Graf graf(n, m, s);
graf.bfs(s);
f.close();
g.close();
}
if(problema == 2) // 100
{
int n, m;
f.open ("dfs.in", std::ifstream::in);
g.open ("dfs.out", std::ifstream::out);
f >> n >> m;
vector<bool> vizitat;
vizitat.resize(n + 1);
for(int index = 1; index <= n; index++)
vizitat[index] = false;
Graf graf(n, m);
int contor = 0;
for(int index = 1; index <= n; index++)
{
if(vizitat[index] == false)
{
graf.dfs(vizitat, index);
contor++;
}
}
g << contor;
f.close();
g.close();
}
if(problema == 3) // 90 - TLE
{
int n, m;
f.open ("biconex.in", std::ifstream::in);
g.open ("biconex.out", std::ifstream::out);
f >> n >> m;
Graf graf(n, m);
graf.biconex();
f.close();
g.close();
}
if(problema == 4) // 70
{
int n, m;
f.open ("ctc.in", std::ifstream::in);
g.open ("ctc.out", std::ifstream::out);
f >> n >> m;
Graf graf(n, m, 0);
vector<int> rezultat;
vector<int> nivel;
vector<int> nivelMinim;
vector<bool> stiva;
vector< vector <int> > output;
stack<int> st;
nivel.resize(n + 1);
nivelMinim.resize(n + 1);
stiva.resize(n + 1);
for(int index = 1; index <= n; index++)
{
nivel[index] = -1;
stiva[index] = false;
}
for(int index = 1; index <= n; index++)
if(nivel[index] == -1)
graf.componenteTareConexe(index, rezultat, nivel, nivelMinim, stiva, st, output, 0);
g << output.size() << "\n";
for(int index = 0; index < output.size(); index++)
{
for(int secondIndex = 0; secondIndex < output[index].size(); secondIndex++)
g << output[index][secondIndex] << " ";
g << "\n";
}
f.close();
g.close();
}
if(problema == 5) // 100
{
int n, m;
f.open ("sortaret.in", std::ifstream::in);
g.open ("sortaret.out", std::ifstream::out);
f >> n >> m;
Graf graf(n, m, 0);
vector<int> output;
vector<bool> vizitat;
vizitat.resize(n + 1);
for(int index = 1; index <= n; index++)
vizitat[index] = false;
for(int index = 1; index <= n; index++)
if(vizitat[index] == false)
graf.sortaret(index, vizitat, output);
for(int index = output.size() - 1; index >= 0; index --)
g << output[index] << " ";
}
if(problema == 6) // 100
{
f.open ("havelhakimi.in", std::ifstream::in);
g.open ("havelhakimi.out", std::ifstream::out);
vector<int> grade;
int n, grad;
f >> n;
grade.resize(n);
for(int index = 0; index < n; index++)
{
f >> grad;
grade.push_back(grad);
}
Graf graf(0, 0, 0);
if(graf.Havel_Hakimi(n, grade))
g << "Secventa de numere poate forma un graf.";
else
g << "Secventa de numere nu poate forma un graf.";
}
if(problema == 7) // 100
{
f.open ("critical.in", std::ifstream::in);
g.open ("critical.out", std::ifstream::out);
int n;
f >> n;
Graf graf(n);
graf.critical();
}
if(problema == 8)
{
f.open ("apm.in", std::ifstream::in);
g.open ("apm.out", std::ifstream::out);
Graf graf;
graf.apm();
}
if(problema == 9)
{
f.open ("disjoint.in", std::ifstream::in);
g.open ("disjoint.out", std::ifstream::out);
Graf graf;
graf.disjoint();
}
if(problema == 10)
{
f.open ("dijkstra.in", std::ifstream::in);
g.open ("dijkstra.out", std::ifstream::out);
Graf graf;
graf.dijkstra();
}
return 0;
}