Pagini recente » Cod sursa (job #2770635) | Cod sursa (job #82536) | Cod sursa (job #1112110) | Cod sursa (job #2336028) | Cod sursa (job #1751831)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
class BCCGraph {
public:
BCCGraph(int size) {
size_ = size;
discovery_time_.resize(size + 1);
low_link_.resize(size + 1);
edges_.resize(size + 1);
is_articulation_point_.resize(size + 1);
}
void AddEdge(int to, int from) {
edges_[to].push_back(from);
edges_[from].push_back(to);
}
void FindBiconnectedComponents() {
current_count_ = 0;
fill(discovery_time_.begin(), discovery_time_.end(), 0);
fill(low_link_.begin(), low_link_.end(), 0);
fill(is_articulation_point_.begin(), is_articulation_point_.end(), 0);
biconnected_components_.clear();
stack_.clear();
Dfs(1, 0);
}
vector<vector<int>> GetBiconnectedComponents() {
return biconnected_components_;
}
bool IsArticulationPoint(int node) {
return is_articulation_point_[node];
}
private:
int current_count_;
int size_;
vector<int> discovery_time_;
vector<int> low_link_;
vector<bool> is_articulation_point_;
vector<vector<int>> edges_;
vector<vector<int>> biconnected_components_;
vector<int> stack_;
void Dfs(int node, int father) {
discovery_time_[node] = low_link_[node] = ++current_count_;
stack_.push_back(node);
for (auto neighbour : edges_[node]) {
if (neighbour != father) {
if (!discovery_time_[neighbour]) {
Dfs(neighbour, node);
low_link_[node] = min(low_link_[node], low_link_[neighbour]);
// The current node is an articulation point
if (low_link_[neighbour] >= discovery_time_[node]) {
is_articulation_point_[node] = 1;
vector<int> new_component;
while (stack_.back() != node) {
new_component.push_back(stack_.back());
stack_.pop_back();
}
new_component.push_back(stack_.back());
biconnected_components_.push_back(new_component);
}
} else {
low_link_[node] = min(low_link_[node], discovery_time_[neighbour]);
}
}
}
}
};
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m;
scanf("%d%d", &n, &m);
BCCGraph graph(n);
for (; m; m--) {
int x, y;
scanf("%d%d", &x, &y);
graph.AddEdge(x, y);
}
graph.FindBiconnectedComponents();
vector<vector<int>> bcc = graph.GetBiconnectedComponents();
printf("%d\n", (int)bcc.size());
for (auto comp : bcc) {
for (auto x : comp) {
printf("%d ", x);
}
printf("\n");
}
return 0;
}