Pagini recente » Cod sursa (job #1254381) | Cod sursa (job #91028) | Cod sursa (job #2393508) | Cod sursa (job #1872028) | Cod sursa (job #3125438)
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100005];
int n, m;
int parent[100005];
int timestamp = 0;
int found[100005];
int low_link[100005];
vector<vector<int>> all_sccs;
vector<vector<int>> bcc;
vector<int> scc;
stack<pair<int, int>> sc;
ifstream in("biconex.in");
ofstream out("biconex.out");
void DFS(int node) {
found[node] = ++timestamp;
low_link[node] = timestamp;
int children = 0;
for (auto neigh : adj[node]) {
if (found[neigh] == -1) {
parent[neigh] = node;
children++;
sc.push({node, neigh});
DFS(neigh);
low_link[node] = min(low_link[neigh], low_link[node]);
if (low_link[neigh] >= found[node]) {
vector<int> current_bcc;
pair<int, int> current_edge = {node, neigh};
pair<int, int> stack_edge = {-1, -1};
while (stack_edge != current_edge) {
stack_edge = sc.top();
sc.pop();
current_bcc.push_back(stack_edge.first);
current_bcc.push_back(stack_edge.second);
}
sort(current_bcc.begin(), current_bcc.end());
auto it = unique(current_bcc.begin(), current_bcc.end());
current_bcc.erase(it, current_bcc.end());
bcc.push_back(current_bcc);
}
} else {
if (neigh != parent[node]) {
low_link[node] = min(low_link[neigh], low_link[node]);
}
}
}
}
int main() {
in >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
in >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
low_link[i] = 1e9;
found[i] = -1;
}
for (int i = 1; i <= n; i++) {
if (found[i] == -1) {
parent[i] = 0;
DFS(i);
}
}
out << bcc.size() << '\n';
for (auto x : bcc) {
for (auto node : x) {
out << node << ' ';
}
out << '\n';
}
}