Pagini recente » Cod sursa (job #3360569) | Cod sursa (job #3363301)
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_set>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m;
vector<vector<int>> graph;
vector<int> time_in, low_time_in;
bitset<(int)(1e5 + 5)> vis;
stack<pair<int, int>> component_edges;
int counter = 0;
vector<unordered_set<int>> answer;
void handle_found_articulation_point(int n1, int n2) {
int top_n1 = 0, top_n2 = 0;
unordered_set<int> connected_component;
while (top_n1 != n1 && top_n2 != n2) {
top_n1 = component_edges.top().first;
top_n2 = component_edges.top().second;
component_edges.pop();
connected_component.insert(top_n1);
connected_component.insert(top_n2);
}
answer.push_back(connected_component);
}
void dfs(int node, int parent) {
vis[node] = 1;
time_in[node] = low_time_in[node] = counter++;
for (int neighbor : graph[node]) {
if (!vis[neighbor]) {
component_edges.push({node, neighbor});
dfs(neighbor, node);
low_time_in[node] = min(low_time_in[node], low_time_in[neighbor]);
if (low_time_in[neighbor] >= time_in[node]) {
handle_found_articulation_point(node, neighbor);
}
} else if (vis[neighbor] && neighbor != parent) {
low_time_in[node] = min(low_time_in[node], time_in[neighbor]);
}
}
}
int main() {
cin >> n >> m;
graph.assign(n + 2, vector<int>());
time_in.assign(n + 2, 0);
low_time_in.assign(n + 2, 0);
for (int i = 1 ; i <= m ; ++i) {
int src, dest; cin >> src >> dest;
graph[src].push_back(dest);
graph[dest].push_back(src);
}
dfs(1, 0);
cout << answer.size() << "\n";
for (auto& connected_component : answer) {
for (auto node : connected_component) {
cout << node << " ";
}
cout << "\n";
}
return 0;
}