Pagini recente » Cod sursa (job #1623646) | Cod sursa (job #1752302) | Cod sursa (job #195419) | Cod sursa (job #1489383) | Cod sursa (job #982884)
Cod sursa(job #982884)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define Nmax 100003
class edge
{
public:
int x;
int y;
};
vector <int> SOL[Nmax];
vector <int> G[Nmax];
vector <int> low(Nmax);
vector <int> dfn(Nmax);
stack <edge> ST;
int N, M, NR;
void read()
{
ifstream f("biconex.in");
f >> N >> M;
for ( int i = 1, a, b; i <= M; ++i )
{
f >> a >> b;
G[a].push_back( b );
G[b].push_back( a );
}
for ( int i = 1; i <= N; ++i )
dfn[i] = -1;
f.close();
}
void biconex( int nod, int fiu )
{
edge a;
NR++;
do
{
a = ST.top();
ST.pop();
SOL[NR].push_back( a.x );
SOL[NR].push_back( a.y );
} while( a.x != nod || a.y != fiu );
}
void DF( int nod, int tata, int number )
{
low[nod] = dfn[nod] = number;
for ( unsigned i = 0; i < G[nod].size(); ++i )
{
if ( G[nod][i] == tata )
continue;
if ( dfn[ G[nod][i] ] == -1 )
{
edge a = { nod, G[nod][i] };
ST.push( a );
DF( G[nod][i], nod, number + 1 );
low[nod] = min( low[nod], low[ G[nod][i] ] );
if ( low[ G[nod][i] ] >= dfn[nod] )
{
biconex( nod, G[nod][i] );
}
}
else
{
low[nod] = min( low[nod], dfn[ G[nod][i] ] );
}
}
}
void print()
{
ofstream g("biconex.out");
g << NR << "\n";
for ( int i = 1; i <= NR; ++i )
{
sort( SOL[i].begin(), SOL[i].end() );
SOL[i].erase( unique( SOL[i].begin(), SOL[i].end() ), SOL[i].end() );
for ( unsigned j = 0; j < SOL[i].size(); ++j )
g << SOL[i][j] << " ";
g << "\n";
}
g.close();
}
int main()
{
read();
DF( 1, 0, 0 );
print();
return 0;
}