Pagini recente » Cod sursa (job #2655984) | Cod sursa (job #1010524) | Cod sursa (job #2611897) | Cod sursa (job #1676193) | Cod sursa (job #2981189)
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#include<algorithm>
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
using namespace std;
const int NMAX = 1e5;
vector<int>g[NMAX + 1], visited, low, tin, mark, ans[NMAX + 1];
int n, m, u, v, timer, cc;
stack<int>stiva;
void find_points(int node, int parent) {
visited[node] = 1;
stiva.push(node);
tin[node] = low[node] = ++timer;
for (auto i : g[node]) {
if (i == parent) continue;
if (visited[i]) low[node] = min(low[node], tin[i]);
else {
find_points(i, node);
low[node] = min(low[node], low[i]);
if (low[i] >= tin[node]) {
cc++;
while (!stiva.empty() && stiva.top() != i)
{
ans[cc].push_back(stiva.top());
stiva.pop();
}
ans[cc].push_back(i);
ans[cc].push_back(node);
}
}
}
}
int main() {
in >> n >> m;
low = tin = mark = visited = vector<int>(n + 1);
while (m--) {
in >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++)
if (!visited[i]) find_points(i, 0);
out << cc << '\n';
for (int i = 1; i <= cc; i++) {
sort(ans[i].begin(), ans[i].end());
for (auto j : ans[i]) out << j << " ";
out << '\n';
}
return 0;
}