Pagini recente » Cod sursa (job #3172833) | Cod sursa (job #1150115) | Cod sursa (job #1915201) | Cod sursa (job #869805) | Cod sursa (job #772172)
Cod sursa(job #772172)
// Un graf biconex este un graf conex din care ,
// dupa ce taiem orice punct ramane tot conex.
// Pentru a afla componentele biconexe trebuie
// sa determinam punctele de articulatie.
// Un punct de articulatie este format din *muchii*
// ( deci un punct de articulatie se afla in mai multe componente )
// Folosim o stiva si in momentul cand in arborele DFS ajungem la
// un nod fara fii cautam drumuri de intoarecere. Drumul de intoarcere
// cu nodul cel mai sus determina componenta biconexa.
// In cazul in care nu avem drumuri de intaorcere din punct ,
// componenta e formata din nod si predecesorul sau.
#include <fstream>
#include <vector>
using namespace std;
ifstream F("biconex.in");
ofstream G("biconex.out");
#define Nmax 100011
#define Mmax 200011
typedef vector<int>::iterator Iter;
vector < int > Rez[Nmax];
vector < int > Leg[Nmax];
vector < int > Stiva;
int Marked[Nmax];
int Turn[Nmax];
int N,M,Co,Return=1<<30;
void Get( int Nod,int Start,int Step )
{
Marked[Nod]=1;
Turn[Nod]=Step;
Stiva.push_back( Nod );
for ( Iter it=Leg[Nod].begin();it!=Leg[Nod].end();++it )
{
if ( Turn[Nod] > Return ) return;
else Return=1<<30;
if ( !Marked[ *it ] )
Get( *it , Start ,Step+1 );
}
if ( Turn[Nod] > Return ) return;
else Return=1<<30;
if ( Nod!=Start )
{
int Lvl=0;
for ( Iter it=Leg[Nod].begin();it!=Leg[Nod].end();++it )
if ( Step - Turn[*it] > Lvl )
Lvl=Step - Turn[*it];
Return=Step - Lvl;
++Co;
while ( Lvl )
{
Rez[Co].push_back( Stiva.back() );
Stiva.pop_back();
--Lvl;
}
Rez[Co].push_back( Stiva.back() );
}
}
int main()
{
F>>N>>M;
for (int x,y;M;--M)
{
F>>x>>y;
Leg[x].push_back( y );
Leg[y].push_back( x );
}
for (int i=1;i<=N;++i)
if ( !Marked[i] )
{
Get( i , i , 0);
while ( Stiva.size() )
Stiva.pop_back();
}
G<<Co<<'\n';
for (int i=1;i<=Co;++i)
{
for ( Iter it=Rez[i].end();it!=Rez[i].begin();--it )
G<< *(it-1) <<' ';
G<<'\n';
}
}