Pagini recente » Rating Dumbrava Alexandru (LeDumbrava) | Cod sursa (job #1909220)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vb = vector<bool>;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
stack<pii> stk;
vector<vi> biconexe;
vector<vi> v;
vi lev, levMin;
vi comp;
vb seen;
inline void read() {
fin >> n >> m;
v = vector<vi>(n + 1);
lev = levMin = vi(n + 1);
seen = vb(n + 1);
for (int i = 1, x, y; i <= m; ++i) {
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
}
void dfs(int node, int father) {
lev[node] = levMin[node] = lev[father] + 1;
seen[node] = 1;
int x1, x2;
for (const int& x: v[node]) {
if (x == father)
continue;
if (!seen[x]) { // tree edge
stk.push({node, x});
dfs(x, node);
levMin[node] = min(levMin[node], levMin[x]);
if (levMin[x] >= lev[node]) {
comp.clear();
do {
x1 = stk.top().first, x2 = stk.top().second;
stk.pop();
comp.push_back(x1);
comp.push_back(x2);
} while (x1 != node && x2 != x);
biconexe.push_back(comp);
}
}
else
levMin[node] = min(levMin[node], lev[x]);
}
}
inline void write() {
fout << biconexe.size() << '\n';
for (auto& cc: biconexe) {
sort(cc.begin(), cc.end());
cc.erase(unique(cc.begin(), cc.end()), cc.end());
for (const int& x: cc)
fout << x << ' ';
fout << '\n';
}
}
int main()
{
read();
dfs(1, 0);
write();
fin.close();
fout.close();
return 0;
}