Pagini recente » Cod sursa (job #3305495) | Cod sursa (job #3354162) | Cod sursa (job #2049779) | Cod sursa (job #3346416) | Cod sursa (job #3336277)
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector<vector<int>> adj, comps;
vector<bool> vis;
vector<int> tin, tmin;
stack<pair<int, int>> edges;
int timer;
void dfs(int u, int p = -1) {
vis[u] = true;
tin[u] = tmin[u] = timer++;
for (int v : adj[u]) {
if (v == p) continue;
if (vis[v]) {
if (tin[v] < tin[u])
edges.push({u, v});
tmin[u] = min(tmin[u], tin[v]);
}
else {
edges.push({u, v});
dfs(v, u);
tmin[u] = min(tmin[u], tmin[v]);
if (tmin[v] >= tin[u]) { // punct critic
vector<int> curr_comp;
set<int> nodes;
pair<int, int> edge = {0, 0};
while (edge.first != u ||edge.second != v) {
edge = edges.top();
edges.pop();
nodes.insert(edge.first);
nodes.insert(edge.second);
}
for (int nd : nodes)
curr_comp.push_back(nd);
comps.push_back(curr_comp);
}
}
}
}
int main() {
timer = 0;
int n, m;
cin >> n >> m;
adj.assign(n + 1, vector<int>());
vis.assign(n + 1, false);
tin.assign(n + 1, -1);
tmin.assign(n + 1, -1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
cout << comps.size() << "\n";
for (auto comp : comps) {
for (int elem : comp)
cout << elem << " ";
cout << "\n";
}
return 0;
}