Pagini recente » Cod sursa (job #980664) | Cod sursa (job #937802) | Cod sursa (job #2485686) | Cod sursa (job #1451773) | Cod sursa (job #2796853)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define Nmax 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M;
bool vizitat[Nmax];
int up[Nmax], nivel[Nmax];
int S[Nmax], top;
vector<int> comp_biconexe[Nmax];
int nr_comp_biconexe;
class Graf{
private:
int Nr_Noduri, Nr_Muchii;
vector<int> matrice_adiacenta[Nmax];
public:
Graf(int N, int M); // constructor
/*
vector < vector<int> > getMatriceAdiacenta()
{
return matrice_adiacenta;
}
*/
void Citire_Graf_Neorientat();
void DFS( int nod, int parinte );
};
// constructor
Graf :: Graf(int N, int M)
{
Nr_Noduri = N;
Nr_Muchii = M;
}
void Graf :: Citire_Graf_Neorientat()
{
for ( int i = 1; i <= Nr_Muchii; i++ )
{
int x, y;
fin >> x >> y;
matrice_adiacenta[x].push_back(y);
matrice_adiacenta[y].push_back(x);
}
}
void Graf :: DFS(int nod, int parinte )
{
vizitat[nod] = 1;
up[nod] = nivel[nod];
S[++top] = nod; // adaugam nodul in stiva
for ( auto i : matrice_adiacenta[nod] )
{
if ( i == parinte ) continue;
if ( vizitat[i] )
up[nod] = min(up[nod], nivel[i]);
else
{
nivel[i] = nivel[nod] + 1;
DFS(i, nod);
if ( up[i] >= nivel[nod] )
{
nr_comp_biconexe++;
while ( S[top] != i && top )
comp_biconexe[nr_comp_biconexe].push_back(S[top--]);
comp_biconexe[nr_comp_biconexe].push_back(S[top--]);
comp_biconexe[nr_comp_biconexe].push_back(nod);
}
up[nod] = min(up[nod], up[i]);
}
}
fout << nr_comp_biconexe << "\n";
for ( int i = 1; i <= nr_comp_biconexe; i++ )
{
for ( auto j : comp_biconexe[i] )
fout << j << " ";
fout << "\n";
}
}
int main()
{
fin >> N >> M;
Graf G(N, M);
G.Citire_Graf_Neorientat();
G.DFS(1, 0);
return 0;
}