Pagini recente » Cod sursa (job #1378707) | Cod sursa (job #2130609) | Cod sursa (job #1722730) | Cod sursa (job #1949528) | Cod sursa (job #3029993)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int NMAX = 1e5;
int n, m;
vector<vector<int>> edges;
vector<set<int>> ans;
int low[NMAX + 5], dpth[NMAX + 5];
stack<pair<int, int>> st;
void cache(int x, int y)
{
set<int> aux;
int tx, ty;
do
{
tx = st.top().first;
ty = st.top().second;
aux.insert(tx);
aux.insert(ty);
st.pop();
}
while(tx != x || ty != y);
ans.push_back(aux);
}
void DFS(int node, int parent, int depth)
{
dpth[node] = depth;
low[node] = depth;
for (auto it : edges[node])
{
if (it == parent)
continue;
if (!dpth[it])
{
st.push({node, it});
DFS(it, node, depth + 1);
low[node] = min(low[node], low[it]);
if (low[it] >= dpth[node])
{
cache(node, it);
}
}
else
low[node] = min(low[node], low[it]);
}
}
int main()
{
cin >> n >> m;
edges.resize(n + 1);
for (int i = 1; i <= m; i++)
{
int a, b;
cin >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
}
DFS(1, 0, 1);
cout << ans.size() << '\n';
for (auto it : ans)
{
for (auto jt : it)
cout << jt << ' ';
cout << '\n';
}
return 0;
}