Pagini recente » Cod sursa (job #2665976) | Cod sursa (job #2203514) | Diferente pentru info-oltenia-2018/individual intre reviziile 16 si 2 | Cod sursa (job #1152247) | Cod sursa (job #1751840)
#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 num_vertices) : num_vertices_(num_vertices) {
discovery_time_.resize(num_vertices + 1);
low_link_.resize(num_vertices + 1);
edges_.resize(num_vertices + 1);
is_articulation_point_.resize(num_vertices + 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) const {
return is_articulation_point_[node];
}
private:
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]) {
FetchComponent(node, neighbour);
}
} else {
low_link_[node] = min(low_link_[node], discovery_time_[neighbour]);
}
}
}
}
void FetchComponent(int node, int son) {
is_articulation_point_[node] = 1;
vector<int> new_component;
while (stack_.back() != son) {
new_component.push_back(stack_.back());
stack_.pop_back();
}
stack_.pop_back();
new_component.push_back(son);
new_component.push_back(node);
biconnected_components_.push_back(new_component);
}
const int num_vertices_;
int current_count_;
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_;
};
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;
}