Pagini recente » Cod sursa (job #480513) | Cod sursa (job #2891062) | Cod sursa (job #2772820) | Cod sursa (job #2227988) | Cod sursa (job #3215310)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out.txt");
const int N = 1e5;
int low[N + 1], discover[N + 1];
vector <int> l[N + 1], g[N + 1];
int n, m, timp, len, x, y;
stack <int> s;
void dfs (int node, int parent)
{
low[node] = discover[node] = ++timp;
s.push(node);
for (auto it : g[node])
{
if (!discover[it])
{
dfs (it, node);
low[node] = min (low[node], low[it]);
if (low[it] >= discover[node])
{
///node e punct de articulatie
++len;
while (!s.empty() && s.top() != it)
l[len].push_back(s.top()), s.pop();
if (!s.empty())
l[len].push_back(s.top()), s.pop();
l[len].push_back(node);
}
if (low[it] > discover[node]);///e bridge
}
else
{
if (it != parent && discover[it] < discover[node])///daca am muchie back si e stramos
low[node] = min (low[node], discover[it]);
}
}
}
int main()
{
fin>> n >> m;
for (int i = 1; i <= m; ++i)
{
fin>> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs (1, 0);
fout << len << '\n';
for (int i = 1; i <= len; ++i, fout<< '\n')
for (auto it : l[i])
fout << it << ' ';
return 0;
}