#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);
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 Graf :: out ()
{
g << noduri << " " << muchii << endl;
for(int i = 0; i < noduri; 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);
}
}
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);
}
}
int main()
{
int problema = 4;
if(problema == 1)
{
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)
{
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)
{
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)
{
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();
}
return 0;
}