Pagini recente » Cod sursa (job #455481) | Cod sursa (job #470561) | Cod sursa (job #3000209) | Cod sursa (job #2540608) | Cod sursa (job #446219)
Cod sursa(job #446219)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
const char *in = "biconex.in";
const char *out = "biconex.out";
const int DIM = 2800000;
const int NMAX = 100005;
typedef vector<int>::iterator IT;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
template <class T>
T minim (T a, T b)
{
return ((a) < (b) ? (a) : (b));
}
int N, M;
VI L[NMAX], level, low;
VVI SOL;
stack< pair<int,int> > st;
void Push( const int X, const int Y)
{
VI tmp;
int x, y;
do
{
x = st.top().first, y = st.top().second;
st.pop();
tmp.push_back(x), tmp.push_back(y);
} while (x != X || y != Y );
SOL.push_back (tmp);
}
void DF( int nod, int fnod, int niv)
{
IT it;
level[nod] = low[nod] = niv;
for ( it = L[nod].begin(); it != L[nod].end(); ++it)
{
if (*it == fnod) continue;
if (level[*it] == -1) /* muchie de arbore */
{
st.push(make_pair (nod, *it));
DF (*it, nod, niv+1);
low[nod] = minim( low[nod], low[*it]);
if (low[*it] >= level[nod] ) /* nod - punct de articulatie */
Push( nod, *it);
}
else
low[nod] = minim( low[nod], level[*it]); /* muchie de intoarcere */
}
}
int main(void)
{
freopen (in, "r", stdin);
freopen (out, "w", stdout);
char buf[DIM];
int X, Y, poz;
/* Parsing the input reading */
fread (buf, 1, DIM, stdin);
#define cit(x) \
{ \
x = 0; \
while (buf[poz] < '0') \
{ \
++poz; \
if (poz == DIM) { \
fread (buf, 1, DIM, stdin); poz = 0; } \
} \
while (buf[poz] >= '0') \
{ \
x = x*10 + buf[poz] - '0'; \
if (++poz == DIM) { \
fread (buf, 1, DIM, stdin); poz = 0; } \
} \
}
cit(N) cit(M)
for ( ; M; --M)
{
cit(X) cit(Y)
L[X].push_back (Y);
L[Y].push_back (X);
}
level.resize( N + 1 );
level.assign( N + 1, -1);
low.resize (N+1);
DF(1,0,0);
size_t i = SOL.size(), j;
printf ("%d\n", i);
for (i = 0; i < SOL.size(); ++i)
{
sort(SOL[i].begin(), SOL[i].end());
SOL[i].erase(unique(SOL[i].begin(), SOL[i].end()), SOL[i].end());
for (j = 0; j < SOL[i].size(); ++j)
printf ( "%d ", SOL[i][j]);
printf ("\n");
}
return 0;
}