Pagini recente » Cod sursa (job #130697) | Cod sursa (job #1805880) | Cod sursa (job #1621063) | Cod sursa (job #1879790) | Cod sursa (job #2155742)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int MAXN = 100005;
int n, m, t, time[MAXN], low[MAXN], ncb;
bool viz[MAXN];
vector<int> g[MAXN];
vector<int> cb[MAXN];
stack<int> st;
void save_cb(int x) {
ncb++;
while (st.top() != x) {
cb[ncb].push_back(st.top());
st.pop();
}
cb[ncb].push_back(x);
}
void dfs(int x, int px) {
viz[x] = true;
time[x] = ++t;
low[x] = time[x];
st.push(x);
for (int &y : g[x]) {
if (y == px) continue;
if (!viz[y]) {
dfs(y, x);
low[x] = min(low[x], low[y]);
if (low[y] >= time[x]) {
save_cb(x);
}
} else {
low[x] = min(low[x], time[y]);
}
}
}
int main()
{
in >> n >> m;
for (int i = 1, x, y; i <= m; ++i) {
in >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; ++i) {
if (!viz[i]) {
dfs(i, -1);
}
}
out << ncb << "\n";
for (int i = 1; i <= ncb; ++i) {
sort(cb[i].begin(), cb[i].end(), less<int>());
for (int &y : cb[i]) out << y << " ";
out << "\n";
}
return 0;
}