Pagini recente » Cod sursa (job #922494) | Cod sursa (job #460231) | Cod sursa (job #1209203) | Cod sursa (job #749551) | Cod sursa (job #772200)
Cod sursa(job #772200)
// 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 sau muchiile critice.
// Un punct de articulatie este format din *muchii*
// ( deci un punct de articulatie se afla in mai multe componente )
// Punctele de articulatie se mai numesc si pnct. critice.
// Un pnct. este critic , daca si numai daca de la cel putin un fiu
// al sau se poate ajunge mai sus in arbore decat la punctul respectiv.
// O muchie este critica daca este nivelul minim accesibil al nodului de mai jos
// este mai mic decat cel al tatului in arborele DFS.
// Parcurgem arborele DFS si atunci cand avem un nod care nu poate ajunge mai sus
// de tata am gasit o componenta conexa. Acest nod a fost unul de legatura.
#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];
int StivaX[Nmax], StivaY[Nmax], L;
int Marked[Nmax];
int Mark[Nmax];
int Best[Nmax];
int Niv[Nmax];
int Dad[Nmax];
int N,M,Co;
void Get( int Nod )
{
Marked[Nod]=1;
Best[Nod]=Niv[Nod];
for ( Iter it=Leg[Nod].begin();it!=Leg[Nod].end();++it )
if ( !Marked[ *it ] )
{
Niv[ *it ] = Niv[Nod] + 1;
Dad[ *it ] = Nod ;
StivaX[++L]=Nod;
StivaY[L]= *it ;
Get( *it );
Best[Nod] = min( Best[Nod] , Best[ *it ] );
if ( Best[ *it ] >= Niv[ Nod ] )
{
++Co;
for ( ; L >= 0 && ( StivaX[L+1] != Nod || StivaY[L+1] != *it ); L-- )
{
if ( Mark[ StivaY[L] ] != Co )
{
Mark[ StivaY[L] ] = Co;
Rez[Co].push_back( StivaY[L] );
}
if ( Mark[ StivaX[L] ] != Co )
{
Mark[ StivaX[L] ] = Co;
Rez[Co].push_back( StivaX[L] );
}
}
}
}
else
if ( *it != Dad[ Nod ] )
Best[Nod] = min( Best[Nod], Niv[ *it ] );
}
int main()
{
F>>N>>M;
for (int x,y;M;--M)
{
F>>x>>y;
Leg[x].push_back( y );
Leg[y].push_back( x );
}
Get( 1 );
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';
}
}