Pagini recente » Cod sursa (job #673079) | Cod sursa (job #1760252) | Cod sursa (job #3120836) | Cod sursa (job #2081092) | Cod sursa (job #3297869)
#include <iostream>
#include <vector>
#include <stack>
#include <set>
const int NMAX = (int)1e5 + 5;
int n, m;
int timestamp;
std::vector<int> adj[NMAX];
std::vector<int> discovery_time;
std::vector<int> low_link;
std::vector<int> parent;
std::stack<std::pair<int, int> > edge_stack;
std::vector<std::set<int> > bccs;
void dfs_bcc(int node, int p) {
discovery_time[node] = low_link[node] = timestamp++;
parent[node] = p;
for (auto &neigh : adj[node]) {
if (neigh == p) {
continue;
}
if (discovery_time[neigh] != -1 && discovery_time[neigh] < discovery_time[node]) {
// means it's a back-edge
edge_stack.push({node, neigh});
low_link[node] = std::min(low_link[node], discovery_time[neigh]);
}
if (discovery_time[neigh] == -1) {
// neigh is unvisited
edge_stack.push({node, neigh});
dfs_bcc(neigh, node);
// node can reach what neigh can
low_link[node] = std::min(low_link[node], low_link[neigh]);
if (low_link[neigh] >= discovery_time[node]) {
// bcc found
std::set<int> vertices;
while (!edge_stack.empty()) {
std::pair<int, int> edge = edge_stack.top();
edge_stack.pop();
vertices.insert(edge.first);
vertices.insert(edge.second);
if (edge.first == node && edge.second == neigh) {
break;
}
}
bccs.push_back(vertices);
}
}
}
}
int main(void)
{
#ifndef LOCAL
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
#endif
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
discovery_time.resize(n + 1);
parent.resize(n + 1);
low_link.resize(n + 1);
discovery_time.assign(discovery_time.size(), -1); // unvisited
low_link.assign(low_link.size(), -1);
parent.assign(parent.size(), 0);
for (int i = 1; i <= n; ++i) {
if (discovery_time[i] == -1) {
dfs_bcc(i, 0);
}
}
std::cout << bccs.size() << '\n';
for (auto &bcc : bccs) {
bool first = true;
for (auto &elem : bcc) {
if (!first) {
std::cout << " ";
}
std::cout << elem;
first = false;
}
std::cout << '\n';
}
return 0;
}