Pagini recente » Cod sursa (job #363159) | Cod sursa (job #2971660) | Cod sursa (job #2540719) | Cod sursa (job #2638112) | Cod sursa (job #2954316)
#include <bits/stdc++.h>
#ifdef BLAT
#include "debug/debug.hpp"
#else
#define debug(x...)
#endif
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
using Graph = vector <vector <int>>;
void append_bcc(int u, int v, vector <vector <int>> &bcc, stack <pair <int, int>> &st) {
vector <int> comp;
pair <int, int> top;
do {
top = st.top();
comp.push_back(top.second);
st.pop();
} while (top != make_pair(u, v));
if (comp.size() == 1)
comp.push_back(u);
bcc.push_back(comp);
}
void dfs(int node, Graph &g, vector <int> &d, vector <int> &l,
stack <pair <int, int>> &st, vector <vector <int>> &bcc, int parent = 0) {
d[node] = l[node] = 1 + d[parent];
for (auto to : g[node]) {
if (d[to] == 0) {
st.push(make_pair(node, to));
dfs(to, g, d, l, st, bcc, node);
l[node] = min(l[node], l[to]);
if (l[to] >= d[node])
append_bcc(node, to, bcc, st);
} else if (to != parent) {
if (d[to] < d[node]) {
st.push(make_pair(node, to));
l[node] = min(l[node], d[to]);
}
}
}
}
int main() {
int n, m;
in >> n >> m;
Graph g(1 + n);
for (int i = 0; i < m; i++) {
int x, y;
in >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
vector <int> depth(1 + n), low(1 + n);
stack <pair <int, int>> st;
vector <vector <int>> bcc;
dfs(1, g, depth, low, st, bcc);
out << bcc.size() << '\n';
for (auto comp : bcc) {
for (auto it : comp)
out << it << ' ';
out << '\n';
}
in.close();
out.close();
return 0;
}