Pagini recente » Cod sursa (job #1702221) | Cod sursa (job #1982844) | Cod sursa (job #1258596) | Cod sursa (job #205717) | Cod sursa (job #936846)
Cod sursa(job #936846)
#include<fstream>
#include<vector>
#include<stack>
#define NMAX 100005
#define pb push_back
#define forit(it, v) for( typeof((v).begin()) it = (v).begin(); it != (v).end(); ++ it)
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,numb;
vector <int> graph[NMAX],solution[NMAX];
stack <int> Stack;
int Level[NMAX],Low[NMAX];
void read( void )
{
f>>n>>m;
for(int i(1) ; i <= m ; ++i )
{
int x,y;
f>>x>>y;
graph[x].pb(y);
graph[y].pb(x);
}
f.close();
}
void ClearTheStack ( int x , int y )
{
while( !Stack.empty() && Stack.top() != y )
{
solution[numb].pb(Stack.top());
Stack.pop();
}
solution[numb].pb(y);
solution[numb++].pb(x);
if( !Stack.empty() )
Stack.pop();
}
void DepthFirstSearch( int Son , int Father )
{
vector <int> ::iterator it;
Low[Son]=Level[Son];
forit(it,graph[Son])
{
if( *it == Father ) continue;
if( !Level[*it] )
{
Stack.push(*it);
Level[*it]=Level[Son]+1;
DepthFirstSearch(*it,Son);
Low[Son]= min ( Low[Son],Low[*it] );
if ( Low[ *it ] >= Level[Son] )
ClearTheStack( Son , *it );
}
else
Low[Son]=min ( Low[Son] ,Low[ *it ] );
}
}
void write ( void )
{
vector <int> ::iterator it;
g<<numb<<"\n";
for(int i(0); i < numb; ++i )
{
forit(it,solution[i])
g<<*it<<" ";
g<<"\n";
}
g.close();
}
int main( void )
{
read();
Stack.push(1);
DepthFirstSearch(1,0);
write();
return 0;
}