Pagini recente » Cod sursa (job #434149) | Cod sursa (job #316351) | Cod sursa (job #1717387) | Cod sursa (job #37113) | Cod sursa (job #650998)
Cod sursa(job #650998)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fi ("biconex.in");
ofstream fo ("biconex.out");
const int dim = 100005;
int N, M, NB, NS, niv[dim], low[dim];
struct { int n, f; } S[dim<<1];
vector <int> B[dim<<1], V[dim];
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 bico (int ns, int fs)
{
int n, f;
NB++;
do
{
n = S[NS].n;
f = S[NS].f;
B[NB].push_back (S[NS].n);
B[NB].push_back (S[NS].f);
--NS;
} while ( !(n == ns && f == fs) );
}
void dfs (int n, int t)
{
niv[n] = low[n] = niv[t] + 1;
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;
dfs (f, n);
low[n] = min (low[n], low[f]);
if (niv[n] <= low[f])
bico (n, f);
}
else
low[n] = min (low[n], niv[f]);
}
}
void afi ()
{
fo << NB << '\n';
for (int i = 1; i <= NB; i++)
{
sort (B[i].begin(), B[i].end());
fo << B[i][0] << ' ';
for (int j = 1; j < B[i].size(); j++)
if (B[i][j] != B[i][j-1])
fo << B[i][j] << ' ';
fo << '\n';
}
}
int main ()
{
cit ();
dfs (1, 0);
afi ();
return 0;
}