Pagini recente » Cod sursa (job #1820415) | Cod sursa (job #2718385) | Cod sursa (job #2672342) | Cod sursa (job #1713662) | Cod sursa (job #3030016)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, i, j, ncbc, x, y;
vector <vector <int> > g;
vector <set <int> > cbc;
set <int> toPush;
vector <int> viz, lvl, t, mnl;
stack <pair <int, int> > s;
void dfs (int x, int l)
{
viz[x] = 1;
lvl[x] = l;
mnl[x] = l;
for (auto it : g[x])
{
if (viz[it] == 0)
{
s.push({x, it});
dfs (it, l+1);
mnl[x] = min(mnl[x], mnl[it]);
if (mnl[it] >= lvl[x])
{
ncbc++;
toPush.clear();
int xx, yy;
do
{
xx = s.top().first, yy = s.top().second;
s.pop();
toPush.insert(xx); toPush.insert(yy);
}
while (xx != x || yy != it);
cbc.push_back(toPush);
}
}
else if (it != t[x])
{
mnl[x] = min(mnl[x], lvl[it]);
}
}
}
int main()
{
fin >> n >> m; g.resize(n+1); cbc.resize(1); t.resize(n+1); viz.resize(n+1); lvl.resize(n+1); mnl.resize(n+1);
for (i = 1; i <= m; i++)
{
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (i = 1; i <= n; i++)
{
if (!viz[i])
dfs (i, 1);
}
fout << ncbc << '\n';
for (i = 1; i <= ncbc; i++)
{
for (auto it : cbc[i])
fout << it << ' ';
fout << '\n';
}
return 0;
}