Pagini recente » Cod sursa (job #1671358) | Cod sursa (job #3229360) | Cod sursa (job #2864390) | Cod sursa (job #3155039) | Cod sursa (job #1752063)
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in" );
ofstream g("biconex.out");
int DFN[100001], LowestAncestor[100001], NrNoduri, NrMuchii;
void PrintComp(int);
void CompBiconexe(int X, int TataX);
int x, y, NrComp;
stringstream OUT;
stack<int> Noduri;
vector<int> A[100001];
int main()
{
f >> NrNoduri >> NrMuchii;
for ( int i=1 ; i<=NrMuchii ; ++i )
{
f >> x >> y;
A[x].push_back(y);
A[y].push_back(x);
}
CompBiconexe(1, 0);
g << NrComp << '\n';
g << OUT.str();
}
void CompBiconexe(int X, int TataX)
{
static int DFCOUNTER = 0;
LowestAncestor[X] = DFN[X] = ++DFCOUNTER;
for ( vector<int>::iterator it = A[X].begin() ; it!=A[X].end() ; ++it )
{
int vecin = *it;
if ( vecin != TataX && DFN[vecin] == 0 ) //Nod nevizitat
Noduri.push( vecin );
if ( vecin != TataX && DFN[vecin] != 0 ) //[X, vecin] muchie de intoarcere
LowestAncestor[X] = min(LowestAncestor[X], DFN[vecin]);
if ( !DFN[vecin] ) //Daca vecinul nu a mai fost vizitat
{
CompBiconexe( vecin, X );
LowestAncestor[X] = min(LowestAncestor[X], LowestAncestor[vecin]);
if ( LowestAncestor[vecin] >= DFN[X] )
{
PrintComp(X);
NrComp++;
}
}
}
}
void PrintComp(int Last)
{
while ( !Noduri.empty() && Noduri.top() != Last )
{
OUT << Noduri.top() << ' ';
Noduri.pop();
}
OUT << Last << '\n';
}