Pagini recente » Borderou de evaluare (job #2357980) | Borderou de evaluare (job #1297266) | Cod sursa (job #70611) | Borderou de evaluare (job #1645708) | Cod sursa (job #2971701)
#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
const int NMAX = 45005;
vector<vector<int>> g;
int n,m,s,e,q,needed[NMAX],tin[NMAX],low[NMAX],timer,articulation[NMAX],viz[NMAX];
void dfs(int node, int parent = 0) {
tin[node] = ++timer;
int kids = 0;
low[node] = tin[node];
for (auto k : g[node]) {
if (k == parent) {
continue;
}
if (tin[k] == 0) {
kids++;
dfs(k, node);
if (low[k] >= tin[node]) {
articulation[node] = 1;
}
low[node] = min(low[node] , low[k]);
} else {
low[node] = min(low[node] , tin[k]);
}
}
if (parent == 0) {
articulation[node] = kids > 1;
}
}
vector<vector<int>> comps;
void get_comps(int node, int id) {
viz[node] = 1;
for (auto k : g[node]) {
if (viz[k] == 1) continue;
if (articulation[node] == 0) {
comps[id].push_back(k);
get_comps(k,id);
} else {
comps.push_back({node, k});
get_comps(k,(int)comps.size() - 1);
}
}
}
int main() {
in >> n >> m;
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);
}
dfs(1);
if (articulation[1] == 0) {
comps.push_back({1});
}
get_comps(1,0);
out << comps.size() << "\n";
for (auto k : comps) {
for (auto y : k) {
out << y << " ";
}
out << "\n";
}
}