Pagini recente » Cod sursa (job #542528) | Cod sursa (job #2458222) | Cod sursa (job #3183076) | Cod sursa (job #1463835) | Cod sursa (job #441876)
Cod sursa(job #441876)
/*
* File: main.cpp
* Author: VirtualDemon
*
* Created on April 13, 2010, 4:08 PM
*/
#include <stack>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#define SIZE 8219
#define Nmax 100000
/*
*
*/
using namespace std;
ifstream in;
typedef pair< int, int > pr;
char file[SIZE];
int N, ifile, idx, ccount;
int dfn[Nmax], lowlink[Nmax];
stack< pr > S;
vector< vector< int > > G, BCC;
inline void read( int& x )
{
x=0;
while( file[ifile] < '0' || file[ifile] > '9' )
if( ++ifile == SIZE )
{
in.read( file, SIZE );
ifile=0;
}
while( file[ifile] >= '0' && file[ifile] <= '9' )
{
x=x*10+file[ifile]-'0';
if( ++ifile == SIZE )
{
in.read( file, SIZE );
ifile=0;
}
}
}
inline void GetBiconexC( int x, int f )
{
pr vertex, current( x, f );
vector< bool > uz( N );
BCC.resize(ccount+1);
do
{
vertex=S.top(); S.pop();
if( !uz[vertex.first] )
{
BCC[ccount].push_back(vertex.first+1);
uz[vertex.first]=true;
}
if( !uz[vertex.second] )
{
BCC[ccount].push_back(vertex.second+1);
uz[vertex.second]=true;
}
}while( vertex != current );
++ccount;
}
inline void DFS( int x )
{
vector< int >::const_iterator it=G[x].begin(), iend=G[x].end();
dfn[x]=lowlink[x]=(++idx);
for( ; it < iend; ++it )
{
if( !dfn[*it] )
{
S.push( pr( *it, x ) );
DFS( *it );
lowlink[x]=min( lowlink[x], lowlink[*it] );
if( lowlink[*it] >= dfn[x] )
GetBiconexC( *it, x );
}
else lowlink[x]=min( lowlink[x], dfn[*it] );
}
}
int main(int argc, char** argv)
{
int M, x, y;
in.open( "biconex.in" );
read(N); read(M);
G.resize(N);
for( ; M; --M )
{
read(x); read(y);
--x, --y;
G[x].push_back(y);
G[y].push_back(x);
}
for( x=0; x < N; ++x )
if( !dfn[x] )
DFS( x );
ofstream out( "biconex.out" );
out<<ccount<<'\n';
for( x=0; x < ccount; ++x )
{
copy( BCC[x].begin(), BCC[x].end(), ostream_iterator<int>( out, " " ) );
out<<'\n';
}
return EXIT_SUCCESS;
}