Pagini recente » Cod sursa (job #1273644) | Cod sursa (job #2294952) | Cod sursa (job #2703693) | Cod sursa (job #1269028) | Cod sursa (job #1156718)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
#define NMAX 100001
#define mp make_pair
#define pb push_back
#define nod1 first
#define nod2 second
using namespace std;
int N, M, i, j, x, y;
int Low[NMAX];
int Level[NMAX];
int T[NMAX];
int Written[NMAX];
vector< int > G[NMAX];
vector< vector < int > > Comp;
stack< pair< int, int > > Muchii;
bool USED[NMAX];
inline void MemComp( int X, int Y )
{
vector< int > C;
pair< int, int > Mct, M1 = mp( X, Y ), M2 = mp( Y, X );
do
{
Mct = Muchii.top(); //iau o muchie din stiva
C.pb( Mct.nod1 ); //ii memorez nodurile in vectorul pentru componenta biconexa noua
C.pb( Mct.nod2 );
Muchii.pop(); //scot muchia din stiva
}
while( Mct != M1 && Mct != M2 ); //pana ajung la muchia (*it - NOD)
Comp.pb( C ); //inserez componenta biconexa nou gasita in vectorul de componente
}
inline void DF( int NOD )
{
USED[NOD] = true;
Low[NOD] = Level[NOD];
for( vector< int >::iterator it = G[NOD].begin(); it != G[NOD].end(); it++ )
{
if( *it != T[NOD] && Level[NOD] > Level[*it] )
Muchii.push( mp( *it, NOD ) ); //introduc muchia in stiva
if( !USED[*it] )
{
Level[*it] = Level[NOD] + 1;
T[*it] = NOD;
DF( *it );
if( Low[NOD] > Low[*it] )
Low[NOD] = Low[*it];
if( Low[*it] >= Level[NOD] )
MemComp( *it, NOD ); //am gasit un punct de articulatie (NOD) deoarece *it (un fiu de-al nodului) nu ajunge mai sus de el in arborele DF
}
else if( *it != T[NOD] && Low[NOD] > Level[*it] )
Lowest[NOD] = Level[*it];
}
}
int main()
{
ifstream in("cbiconexe.in");
ofstream out("cbiconexe.out");
in >> N >> M;
while( M-- )
{
in >> x >> y;
G[x].pb( y );
G[y].pb( x );
}
memset( USED, false, sizeof(USED) );
Level[1] = 1;
DF( 1 );
out << Comp.size() << '\n';
for( i=0; i<Comp.size(); i++ ) //pentru fiecare componenta biconexa in parte
{
for( j=0; j<Comp[i].size(); j++ )
Written[Comp[i][j]] = i; //marchez nodurile din componenta biconexa curenta pentru afisare
for( j=0; j<Comp[i].size(); j++ )
if( Written[Comp[i][j]] == i )
{
out << Comp[i][j] << ' '; //afisez nodul din componenta biconexa
Written[Comp[i][j]] = -1; //il marchez cu -1 ca sa nu il mai afisez a doua oara
}
out << '\n';
}
return 0;
}