Pagini recente » Cod sursa (job #2936556) | Cod sursa (job #525305) | Cod sursa (job #2896682) | Cod sursa (job #1150516) | Cod sursa (job #2897011)
#include <bits/stdc++.h>
#define INF ((int)1e9)
#define NMAX ((int)1e5)
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector<int> adj[NMAX + 1];
vector<unordered_set<int>> all_bccs;
void dfs(int node, vector<int> &parent, int ×tamp, vector<int> &found, vector<int> &low_link,
stack<pair<int, int>> &edges) {
found[node] = ++timestamp;
low_link[node] = found[node];
int children = 0;
for (auto it = adj[node].begin(); it != adj[node].end(); ++it) {
int next_node = *it;
if (parent[next_node] != -1) {
if (next_node != parent[node]) {
low_link[node] = min(low_link[node], found[next_node]);
}
continue;
}
parent[next_node] = node;
++children;
edges.push({node, next_node});
dfs(next_node, parent, timestamp, found, low_link, edges);
low_link[node] = min(low_link[node], low_link[next_node]);
if (low_link[next_node] >= found[node]) {
unordered_set<int> bcc_nodes;
while (true) {
pair<int, int> curr_edge = edges.top();
edges.pop();
bcc_nodes.insert(curr_edge.first);
bcc_nodes.insert(curr_edge.second);
if (curr_edge == make_pair(node, next_node)) {
break;
}
}
all_bccs.push_back(bcc_nodes);
}
}
}
void tarjan_bcc(vector<int> &parent, vector<int> &found, vector<int> &low_link) {
for (int i = 0; i <= n; ++i) {
parent[i] = -1;
found[i] = INF;
low_link[i] = INF;
}
stack<pair<int, int>> edges;
int timestamp = 0;
for (int i = 1; i <= n; ++i) {
if (parent[i] == -1) {
parent[i] = i;
dfs(i, parent, timestamp, found, low_link, edges);
}
}
}
int main(void) {
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int src, dest;
fin >> src >> dest;
adj[src].push_back(dest);
adj[dest].push_back(src);
}
vector<int> parent(n + 1);
vector<int> found(n + 1);
vector<int> low_link(n + 1);
tarjan_bcc(parent, found, low_link);
fout << all_bccs.size() << "\n";
for (size_t i = 0; i < all_bccs.size(); ++i) {
for (auto it = all_bccs[i].begin(); it != all_bccs[i].end(); ++it) {
fout << *it << " ";
}
fout << "\n";
}
return 0;
}