Pagini recente » Cod sursa (job #2252970) | Cod sursa (job #2194478) | Cod sursa (job #1085810) | Cod sursa (job #2805523) | Cod sursa (job #2971688)
#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;
comps[id].push_back(node);
for (auto k : g[node]) {
if (viz[k] == 0) {
if (articulation[k] == 0) {
get_comps(k , id);
} else {
comps.push_back({});
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);
}
in >> s >> e >> q;
dfs(s);
comps.push_back({});
get_comps(1 , 0);
out << comps.size() << "\n";
for (auto k : comps) {
for (auto y : k) {
out << y << " ";
}
out << "\n";
}
}