#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);
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_min(int muchie[], bool ales[]);
};
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);
}
}
Graf :: Graf (int numar_noduri, int numar_muchii, string apm)
{
noduri = numar_noduri;
muchii = numar_muchii;
int nod_1, nod_2;
lista.resize(numar_noduri + 1);
for(int index = 1; index < noduri + 1; index++)
for(int secondIndex = 1; secondIndex < noduri + 1; secondIndex++)
lista[index].push_back(0);
for(int index = 0; index < numar_muchii; index++)
{
f >> nod_1 >> nod_2 >> lista[nod_1][nod_2];
lista[nod_2][nod_1] = lista[nod_1][nod_2];
}
}
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 parinte[noduri + 1], muchie[noduri + 1]; // parinte - contine arborele de cost minim || muchie - contine muchia minima
bool ales[noduri + 1]; // ales - vector de bool pentru a verifica daca o muchie a fost adaugata sau nu
for(int index = 1; index < noduri + 1; index++)
{
muchie[index] = INT_MAX; // Initializam totul cu o valaoare foarte mare pentru a putea sa determinam minimul
ales[index] = false; // Marcam tot vectorul de muchii alese cu false
}
muchie[1] = 0; // Mereu includem prima muchie in vector
parinte[1] = -1; // Primul nod e radacina deci parintele lui e -1
for(int index = 1; index < noduri; index++)
{
int nod = apm_min(muchie, ales); // Alegem cea mai mica muchie
ales[nod] = true; // O marcam ca adaugata in vector
for(int secondIndex = 1; secondIndex < noduri + 1; secondIndex++)
if(lista[nod][secondIndex] && ales[secondIndex] == false && lista[nod][secondIndex] < muchie[secondIndex]) // Determinam cea mai mica muchie curenta
{
parinte[secondIndex] = nod;
muchie[secondIndex] = lista[nod][secondIndex];
}
}
int sum = 0;
for(int index = 1; index < noduri + 1; index++)
sum = sum + muchie[index]; // Calculam suma costurilor
g << sum << endl << noduri - 1; // Afisam suma si numarul de muchii
for(int index = 1; index < noduri + 1; index++)
g << endl << parinte[index] << " " << index; // Afisam muchiile din arbore
}
int Graf :: apm_min(int muchie[], bool ales[])
{
int minim = INT_MAX, min_index; // Initializam minimul cu o valaoare foarte mare pentru a putea sa il determinam
for(int index = 1; index < noduri + 1; index++)
if(ales[index] == false && muchie[index] < minim) // Determinam cea mai mica muchie
{
minim = muchie[index];
min_index = index;
}
return min_index; // Dam return la indicele minimului
}
int main()
{
int problema = 8;
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);
int n, m;
string graf_apm = "apm";
f >> n >> m;
Graf graf(n, m, graf_apm);
graf.apm();
}
return 0;
}