Pagini recente » Cod sursa (job #720200) | Cod sursa (job #2487161) | Cod sursa (job #2087583) | Cod sursa (job #1402849) | Cod sursa (job #2737890)
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int n, m, back[100002], lvl[100002], viz[100002], nr;
stack<pair<int, int> >st;
vector<int>comp[100002], G[100002];
void dfs (int x, int p) {
viz[x] = 1;
lvl[x] = lvl[p] + 1;
back[x] = lvl[x];
for (auto it : G[x]) {
if (!viz[it]) {
st.push({x, it});
dfs(it, x);
if (back[it] >= lvl[x]) {
nr++;
while (st.top() != make_pair(x, it)) {
comp[nr].push_back(st.top().first);
comp[nr].push_back(st.top().second);
st.pop();
}
comp[nr].push_back(x);
comp[nr].push_back(it);
st.pop();
}
back[x] = min(back[it], back[x]);
}
else {
back[x] = min(back[x], lvl[it]);
}
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (!viz[i])
dfs(i, 0);
fout << nr << "\n";
for (int i = 1; i <= nr; i++) {
sort(comp[i].begin(), comp[i].end());
for (int j = 0; j < comp[i].size(); j++)
if (!j || comp[i][j] != comp[i][j - 1])
fout << comp[i][j] << " ";
fout << "\n";
}
return 0;
}