Pagini recente » Cod sursa (job #927089) | Cod sursa (job #778489) | Cod sursa (job #2886497) | Cod sursa (job #2792199) | Cod sursa (job #1365758)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
fstream f("biconex.in", ios::in);
fstream g("biconex.out", ios::out);
const int nmax = 100010;
vector <int> a[nmax], bicon[nmax];
stack <int> s;
int n, m, i, x, y, viz[nmax], low[nmax], niv[nmax], nrb;
void citire()
{
f >> n >> m;
for (i = 1; i <= m; i++)
{
f >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
}
}
void DFS(int nc, int lvl)
{
viz[nc] = 1;
low[nc] = lvl;
niv[nc] = lvl;
s.push(nc);
for (vector <int>::iterator it = a[nc].begin(); it != a[nc].end(); ++it)
{
if (viz[*it])
{
if (niv[*it] < low[nc]) low[nc] = niv[*it];
}
else
{
DFS(*it, lvl + 1);
if (low[*it] < low[nc]) low[nc] = low[*it];
if (niv[nc] <= low[*it])
{
nrb++;
do
{
x = s.top();
s.pop();
bicon[nrb].push_back(x);
} while (x != *it);
bicon[nrb].push_back(nc);
}
}
}
}
int main()
{
citire();
DFS(1, 0);
g << nrb << "\n";
for (i = 1; i <= nrb; i++)
{
for (vector <int>::iterator it = bicon[i].begin(); it != bicon[i].end(); ++it) g << *it << " ";
g << "\n";
}
return 0;
}