Pagini recente » Cod sursa (job #1063648) | Cod sursa (job #90852) | Cod sursa (job #106880) | Cod sursa (job #1497203) | Cod sursa (job #2956836)
#include <bits/stdc++.h>
using namespace std;
const int VMAX = 1e5;
const int EMAX = 1e5;
const int RAND_ROOT = 1, AUX_PARENT = 0;
int depth[1 + VMAX], low[1 + VMAX];
bool visited[1 + VMAX]; vector<int> g[1 + VMAX];
int counter = 0;
vector<int> bc[1 + VMAX];
stack<int> bcStack;
void dfs (int root, int p) {
visited[root] = true;
depth[root] = depth[p] + 1;
low[root] = depth[root];
bcStack.push (root);
for (int node : g[root]) {
if (node != p) {
if (visited[node]) /// back edge
low[root] = min(low[root], depth[node]);
else {
dfs (node, root);
low[root] = min (low[root], low[node]);
if (low[node] >= depth[root]) {
while (bcStack.top () != root) {
bc[counter].push_back (bcStack.top ());
bcStack.pop ();
}
bc[counter].push_back (root);
counter ++;
}
}
}
}
}
int main()
{
ifstream in ("biconex.in");
ofstream out ("biconex.out");
int V, E; in >> V >> E;
for (int i = 1; i <= E; i ++) {
int u, v; in >> u >> v;
g[u].push_back (v);
g[v].push_back (u);
}
dfs (RAND_ROOT, AUX_PARENT);
out << counter << "\n";
for (int idx = 0; idx < counter; idx ++) {
for (int node : bc[idx])
out << node << " ";
out << "\n";
}
return 0;
}