Pagini recente » Cod sursa (job #1454473) | Cod sursa (job #3127669) | Cod sursa (job #2191950) | Cod sursa (job #478193) | Cod sursa (job #1378516)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int MAXN = 100000, MAXM = 200000;
int N, M, level[MAXN+1], low[MAXN+1], viz[MAXN+1], T[MAXN+1], fiiRad = 0, rad, afis[MAXN+1], cnt;
vector <int> G[MAXN+1];
struct muchie
{
int x;
int y;
};
void citire()
{
in>>N>>M;
for(int i = 1; i <= M; i++)
{
int x, y; in>>x>>y;
G[ x ].push_back( y );
G[ y ].push_back( x );
}
}
stack <muchie> st;
void dfs(int nod)
{
viz[ nod ] = 1; low[ nod ] = level[ nod ];
for(int i = 0; i < G[ nod ].size(); i++)
{
int next = G[ nod ][ i ];
if( viz[ next ] == 0 )
{
level[ next ] = level[ nod ] + 1; T[ next ] = nod;
muchie m; m.x = nod; m.y = next; st.push( m );
dfs( next );
if( nod == rad )
fiiRad++;
low[ nod ] = min( low[ nod ], low[ next ] );
if( ( level[ nod ] <= low[ next ] ) || ( next == rad && fiiRad >= 2 ) )
{
//cout<<nod<<' '<<next<<endl;
memset(afis,0,sizeof(afis));
while( !( (st.top()).x == nod && (st.top()).y == next ) )
{
int x = (st.top()).x, y = (st.top()).y;
//cout<<x<<' '<<y<<' ';
if( afis[ x ] == 0 )
out<<x<<' ';
if( afis[ y ] == 0 )
out<<y<<' ';
afis[ x ] = 1, afis[ y ] = 1;
st.pop();
}
if( afis[ nod ] == 0 )
out<<nod<<' ';
if( afis[ next ] == 0 )
out<<next;
//cout<<nod<<' '<<next<<endl;
out<<endl;
st.pop();
cnt++;
}
}
else if( next != T[ next ] )
{
low[ nod ] = min( low[ nod ], level[ next ] );
}
}
}
int main()
{
citire();
rad = 1;
out<<endl;
dfs(rad);
//out<<cnt;
return 0;
}