Pagini recente » Cod sursa (job #1150676) | Cod sursa (job #264164) | Cod sursa (job #1989573) | Cod sursa (job #154756) | Cod sursa (job #2965955)
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("biconex.in");
ofstream out("biconex.out");
#endif
vector<int> tin,up;
vector<vector<int>> sol,g;
const int inf = 1'000'000'005;
int main() {
int n,m;
in >> n >> m;
tin = vector<int>(n + 1, -1);
up = vector<int>(n + 1,inf);
g.resize(n + 1);
for (int i = 1; i <= m; i++) {
int u,v;
in >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
int global_tin_time = 0;
function<void(int,int)> dfs = [&](int node, int parent) {
tin[node] = ++global_tin_time;
up[node] = tin[node];
for (auto k : g[node]) {
if (tin[k] == -1) {
dfs(k, node);
up[node] = min(up[node] , up[k]);
} else {
if (k != parent) {
up[node] = min(up[node] , tin[k]);
}
}
}
};
vector<int> viz(n + 1, 0);
function<void(int,int)> make_groups = [&](int node, int group_id) {
sol[group_id].push_back(node);
viz[node] = 1;
for (auto k : g[node]) {
if (viz[k] == 0) {
if (up[k] > tin[node]) {
sol.push_back({node,k});
sol.push_back({});
make_groups(k , (int)sol.size() - 1);
} else {
make_groups(k , group_id);
}
}
}
};
dfs(1, 0);
sol.push_back({});
make_groups(1, 0);
int nr = 0;
vector<vector<int>> sol2;
for (auto k : sol) {
if (k.size() > 1) {
sol2.push_back(k);
}
}
out << sol2.size() << "\n";
for (auto k : sol2) {
for (auto y : k) {
out << y << " ";
}
out << "\n";
}
}