Pagini recente » Cod sursa (job #2466246) | Cod sursa (job #1704664) | Cod sursa (job #1694773) | Cod sursa (job #1951341) | Cod sursa (job #2049524)
#include <bits/stdc++.h>
using namespace std;
/**
* Author: Simon Lindholm (adapted by Lucian Bicsi)
* Date: 2017-04-17
* License: CC0
* Description: Finds all biconnected components in an undirected graph, and
* runs a callback for the edges in each.
* Callback should operate on vector<pair<int, int>>::iterators.
* In a biconnected component there
* are at least two distinct paths between any two nodes. Note that a node can
* be in several components. An edge which is not in a component is a bridge,
* i.e., not part of any cycle.
*
* To get the articulation points, look for vertices that are in more than 1 BCC.
* Time: O(E + V)
* Status: tested during MIPT ICPC Workshop 2017
*/
struct BCC {
int n, timer = 0;
vector<pair<int, int>> edges;
vector<vector<int>> G;
vector<int> depth, stk;
BCC(int n) : n(n), G(n), depth(n, -1) {}
int AddEdge(int a, int b) {
int ret = edges.size();
edges.emplace_back(a, b);
G[a].push_back(ret);
G[b].push_back(ret);
return ret;
}
template<typename Callback>
void Solve(Callback cb) {
for (int i = 0; i < n; ++i)
if (depth[i] == -1)
dfs(i, -1, 0, cb);
}
template<typename Callback>
int dfs(int node, int pei, int d, Callback cb) {
depth[node] = d; int ret = d;
for (auto ei : G[node]) if (ei != pei) {
int vec = (edges[ei].first ^ edges[ei].second ^ node);
if (depth[vec] != -1) {
ret = min(ret, depth[vec]);
if (depth[vec] < d)
stk.push_back(ei);
} else {
int sz = stk.size();
int low = dfs(vec, ei, d + 1, cb);
ret = min(ret, low);
if (low == d) {
stk.push_back(ei);
cb(vector<int>(stk.begin() + sz, stk.end()));
stk.resize(sz);
} else if (low < d)
stk.push_back(ei);
else {
cb({ei});
}
// else ei is a bridge
}
}
return ret;
}
};
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m; cin >> n >> m;
vector<vector<int>> bccs;
BCC bcc(n);
while (m--) {
int a, b; cin >> a >> b;
bcc.AddEdge(a - 1, b - 1);
}
bcc.Solve([&](vector<int> es) {
vector<int> verts;
for (auto i : es) {
verts.push_back(bcc.edges[i].first);
verts.push_back(bcc.edges[i].second);
}
sort(verts.begin(), verts.end());
verts.erase(unique(verts.begin(), verts.end()), verts.end());
bccs.emplace_back(move(verts));
});
cout << bccs.size() << '\n';
for (auto x : bccs) {
for (auto y : x)
cout << y + 1 << " ";
cout << endl;
}
return 0;
}