Pagini recente » Cod sursa (job #1761688) | Cod sursa (job #1012235) | Cod sursa (job #2620614) | Profil Litean_Roxana | Cod sursa (job #936841)
Cod sursa(job #936841)
#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.top() != y )
{
solution[numb].pb(Stack.top());
Stack.pop();
}
solution[numb].pb(y);
solution[++numb].pb(x);
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] )
{
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[numb])
g<<*it<<" ";
g<<"\n";
}
g.close();
}
int main( void )
{
read();
Stack.push(1);
DepthFirstSearch(1,0);
write();
return 0;
}