Pagini recente » Cod sursa (job #206738) | Cod sursa (job #1470944) | Cod sursa (job #1724850) | Cod sursa (job #1733514) | Cod sursa (job #2811748)
#include<iostream>
#include<vector>
#include<stack>
#include<fstream>
#include<algorithm>
using namespace std;
int n, m, i, j, x, y, low[2000005], dfn[20000005], cnt;
vector<vector<int>>mu, ans;
stack<pair<int, int>>st;
void solve(int x, int y) {
while (st.top().first != x and st.top().second != y) {
ans[cnt].emplace_back(st.top().first);
ans[cnt].emplace_back(st.top().second);
st.pop();
}
ans[cnt].emplace_back(x);
ans[cnt].emplace_back(y);
st.pop();
cnt++;
}
void DFS(int nod, int back, int number) {
low[nod] = dfn[nod] = number;
for (auto k : mu[nod]) {
if (k == back) continue;
if (dfn[k] == -1) {
st.push({ nod,k });
DFS(k, nod, number + 1);
low[nod] = min(low[k], low[nod]);
if (low[k] >= dfn[nod]) solve(nod, k);
}
else low[nod] = min(low[k], low[nod]);
}
}
int main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
cin >> n >> m;
mu.resize(m + 1);
ans.resize(n + 1);
for (i = 1;i <= m;i++)
{
cin >> x >> y;
dfn[i] = -1;
mu[x].emplace_back(y);
mu[y].emplace_back(x);
}
DFS(1, 0, 1);
cout << cnt << '\n';
for (i = 0;i < cnt;i++) {
sort(ans[i].begin(), ans[i].end());
ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
for (auto k : ans[i])
cout << k << " ";
cout << '\n';
}
}