Pagini recente » Cod sursa (job #2240089) | Cod sursa (job #483014) | Cod sursa (job #1874805) | Cod sursa (job #2020682) | Cod sursa (job #662215)
Cod sursa(job #662215)
#include <fstream>
#include <vector>
using namespace std;
ifstream fi ("biconex.in");
ofstream fo ("biconex.out");
const int dim = 100005;
struct muc { int n, f; } S[dim];
vector <int> B[dim], V[dim];
int N, M, C, niv[dim], low[dim], NS;
void cit ()
{
fi >> N >> M;
for (int i = 1, x, y; i <= M; i++)
{
fi >> x >> y;
V[x].push_back (y);
V[y].push_back (x);
}
}
void gasit (int n1, int f1)
{
int n, f;
++C;
do
{
n = S[NS].n;
f = S[NS].f;
B[C].push_back (n);
B[C].push_back (f);
NS--;
} while (n != n1 && f != f1);
sort (B[C].begin(), B[C].end());
for (int i = 1, j = 1; i < B[C].size(); i++)
if (B[C][i] != B[C][i-1])
B[C][++j] = B[C][i];
}
void bic (int n, int k)
{
niv[n] = low[n] = k;
for (int i = 0, f; i < V[n].size(); i++)
{
f = V[n][i];
if (niv[f] == 0)
{
++NS;
S[NS].n = n;
S[NS].f = f;
bic (f, k + 1);
low[n] = min (low[f], low[n]);
if (low[f] <= niv[n])
gasit (n, f);
}
else
{
low[n] = min (low[f], niv[n]);
}
}
}
void afi ()
{
fo << C << '\n';
for (int i = 1, j; i <= C; i++)
{
for (j = 0; j < B[i].size(); j++)
fo << B[i][j] << ' ';
fo << '\n';
}
}
int main ()
{
cit ();
for (int i = 1; i <= N; i++)
if (niv[i] == 0)
bic (i, 1);
afi ();
return 0;
}