Pagini recente » Cod sursa (job #3243284) | Cod sursa (job #2408367) | Cod sursa (job #405185) | Cod sursa (job #1542153) | Cod sursa (job #2798573)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
class Graf
{
private:
int numar_noduri, numar_muchii;
vector <int> lista_adiacenta[100001];
int numar = 0;
public:
void citire();
void dfs_biconex1();
void dfs_biconex2(int, int, int &, stack <int> &, vector <vector <int>>&, vector <int> &, vector <int> &, vector<int> &);
};
/// functie de citire
void Graf :: citire()
{
int capat_stang, capat_drept;
fin >> numar_noduri >> numar_muchii;
for(int i = 0; i < numar_muchii; i++)
{
fin >> capat_stang >> capat_drept;
lista_adiacenta[capat_stang].push_back(capat_drept);
lista_adiacenta[capat_drept].push_back(capat_stang);
}
}
void Graf :: dfs_biconex1()
{
stack <int> st;
vector <int> nivel1(numar_noduri + 1);
vector <int> nivel2(numar_noduri + 1);
vector <int> nivel3(numar_noduri + 1);
vector <vector <int>> componente_biconexe(numar_noduri + 1);
dfs_biconex2(1, 0, numar, st, componente_biconexe, nivel1, nivel2, nivel3);
fout << numar << '\n';
for(int i = 0; i < numar; i++)
{
for(int j = 0; j < componente_biconexe[i].size(); j++)
fout << componente_biconexe[i][j] << " ";
fout << '\n';
}
}
void Graf :: dfs_biconex2(int x, int parinte, int &numar, stack <int> &st, vector <vector <int>>& componente_biconexe, vector <int> &nivel1, vector <int> &nivel2, vector <int> &nivel3)
{
st.push(x);
nivel2[x] = nivel2[parinte] + 1;
nivel1[x] = nivel2[x];
nivel3[x] = 1;
for(int i = 0; i < lista_adiacenta[x].size(); i++)
{
int y = lista_adiacenta[x][i];
if(parinte != y)
if(nivel3[y] == 1)
{
if(nivel1[x] > nivel2[y])
nivel1[x] = nivel1[y];
}
else
{
dfs_biconex2(lista_adiacenta[x][i], x, numar, st, componente_biconexe, nivel1, nivel2, nivel3);
if(nivel1[x] > nivel1[y])
nivel1[x] = nivel1[lista_adiacenta[x][i]];
if(nivel2[x] <= nivel1[y])
{
while(st.top() != y)
{
componente_biconexe[numar].push_back(st.top());
st.pop();
}
componente_biconexe[numar].push_back(y);
componente_biconexe[numar].push_back(x);
st.pop();
numar++;
}
}
}
}
int main()
{
Graf x;
x.citire();
x.dfs_biconex1();
fin.close();
fout.close();
return 0;
}