Pagini recente » Cod sursa (job #2438885) | Cod sursa (job #897759) | Cod sursa (job #3211836) | Cod sursa (job #2677428) | Cod sursa (job #893269)
Cod sursa(job #893269)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fi ("biconex.in");
ofstream fo ("biconex.out");
const int dim = 100005;
int N, M, NB, low[dim], niv[dim];
vector <int> V[dim], R[dim];
stack <pair <int, int> > S;
void cit ()
{
fi >> N >> M;
for (int i = 1, a, b; i <= M; i++)
{
fi >> a >> b;
V[a].push_back (b);
V[b].push_back (a);
}
}
void dfs (int n, int t)
{
low[n] = niv[n] = niv[t] + 1;
for (int i = 0, f; i < V[n].size(); i++)
{
f = V[n][i];
if (t == f) continue;
if (niv[f] == 0)
{
S.push (make_pair (f, n));
dfs (f, n);
low[n] = min (low[n], low[f]);
if (low[f] >= niv[n])
{
int ff = f - 1, nn = n - 1;
NB ++;
while ( !(nn == n && ff == f) )
{
ff = S.top().first;
nn = S.top().second;
S.pop ();
R[NB].push_back (nn);
R[NB].push_back (ff);
}
}
}
else
{
low[n] = min (low[n], niv[f]);
}
}
}
void afi ()
{
fo << NB << '\n';
for (int i = 1, j; i <= NB; i++)
{
sort (R[i].begin(), R[i].end());
fo << R[i][0] << ' ';
for (j = 1; j < R[i].size(); j++)
if (R[i][j] != R[i][j-1])
fo << R[i][j] << ' ';
fo << '\n';
}
}
int main ()
{
cit ();
for (int i = 1; i <= N; i++)
{
if (niv[i] == 0)
{
dfs (i, 0);
}
}
afi ();
return 0;
}