Pagini recente » Cod sursa (job #405039) | Cod sursa (job #2628478) | Cod sursa (job #381706) | Cod sursa (job #2323284) | Cod sursa (job #3230301)
//
// Created by Cristian Constantin on 20.05.2024.
//
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, root = 1, rootChildren;
vector<vector<int>> graph;
vector<bool> visited;
vector<int> depth, low;
stack<pair<int, int>> edges;
vector<vector<int>> biconnectedComponents;
void initialize() {
graph.resize(n + 1);
visited.resize(n + 1, false);
depth.resize(n + 1);
low.resize(n + 1);
}
void readInput() {
fin >> n >> m;
initialize();
int u, v;
for (int i = 0; i < m; ++i) {
fin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
}
void addBiconnectedComponent(int u, int v) {
vector<int> component;
pair<int, int> edge;
do {
edge = edges.top();
edges.pop();
component.push_back(edge.first);
component.push_back(edge.second);
} while (!(edge.first == u && edge.second == v));
sort(component.begin(), component.end());
component.erase(unique(component.begin(), component.end()), component.end());
biconnectedComponents.push_back(component);
}
void dfs(int u, int parent) {
visited[u] = true;
depth[u] = low[u] = (parent == -1 ? 0 : depth[parent] + 1);
for (int v : graph[u]) {
if (v == parent) continue;
if (visited[v]) {
low[u] = min(low[u], depth[v]);
} else {
edges.push({u, v});
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= depth[u]) {
addBiconnectedComponent(u, v);
}
}
}
}
void printBiconnectedComponents() {
fout << biconnectedComponents.size() << '\n';
for (const auto& component : biconnectedComponents) {
for (int node : component) {
fout << node << ' ';
}
fout << '\n';
}
}
int main() {
readInput();
for (int i = 1; i <= n; ++i) {
if (!visited[i]) {
root = i;
rootChildren = 0;
dfs(i, -1);
}
}
printBiconnectedComponents();
return 0;
}