Pagini recente » Cod sursa (job #1346061) | Cod sursa (job #2225778) | Cod sursa (job #1648936) | Cod sursa (job #1635724) | Cod sursa (job #1159433)
#include <fstream>
#include <vector>
const int NMAX = 100005;
const int MMAX = 200005;
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N,M,nv[NMAX],t[NMAX],L[NMAX],x,y,stiva[2][MMAX],lung,rad,nrsol;
bool used[NMAX], afisat[NMAX];
vector <int> v[NMAX];
vector <int> sol[NMAX];
void push(int x, int y)
{
stiva[0][lung] = x;
stiva[1][lung] = y;
lung++;
}
void pop(int *x, int *y)
{
lung--;
*x = stiva[0][lung];
*y = stiva[1][lung];
}
void DFS(int nod)
{
used[nod] = true;
L[nod] = nv[nod];
int x,y;
for (int i = 0; i < v[nod].size(); ++i)
{
if (v[nod][i] != t[nod] && nv[nod] > nv[ v[nod][i] ])
{
push(v[nod][i], nod);
}
if (!used[ v[nod][i] ])
{
nv[ v[nod][i] ] = nv[nod] + 1;
t[ v[nod][i] ] = nod;
DFS( v[nod][i] );
if (L[ v[nod][i] ] < L[nod])
L[nod] = L[ v[nod][i] ];
if (nv[nod] <= L[ v[nod][i] ])
{
nrsol++;
do
{
pop(&x, &y);
//g << x << " " << y << '\n';
sol[nrsol].push_back(x);
sol[nrsol].push_back(y);
}
while ( (x != nod || y != v[nod][i]) && (x != v[nod][i] || y != nod) );
//g << '\n';
}
}
else
if (v[nod][i] != t[nod] && nv[ v[nod][i] ] < L[nod])
L[nod] = nv[ v[nod][i] ];
}
}
int main()
{
f >> N >> M;
for (int i = 1; i <= M; ++i)
{
f >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= N; ++i)
{
if (!used[i])
{
rad = i;
nv[rad] = 1;
DFS(i);
}
}
g << nrsol << '\n';
for (int i = 1; i <= nrsol; ++i)
{
g << sol[i][0] << " ";
g << sol[i][1] << " ";
for (int j = 3; j < sol[i].size() - 1; j+=2)
{
g << sol[i][j] << " ";
}
g << '\n';
}
f.close();
g.close();
return 0;
}