Pagini recente » Cod sursa (job #580443) | Cod sursa (job #416587) | Cod sursa (job #2200193) | Cod sursa (job #2207423) | Cod sursa (job #3230225)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define NMAX 100000
vector <int> g[NMAX + 2];
int viz[NMAX + 2];
int highestNode[NMAX + 2];
int nodes_stack[NMAX + 2];
int stack_top;
int nrComp;
int currTime;
void rst(int n) {
for (int i = 1; i <= n; ++i)
highestNode[i] = viz[i] = 0;
currTime = 0;
stack_top = 0;
}
void dfs(int node, int parent, int print) {
highestNode[node] = parent;
viz[node] = ++currTime;
nodes_stack[++stack_top] = node;
for (int newNode : g[node]) {
if (newNode == parent)
continue;
if (!viz[newNode]) {
dfs(newNode, node, print);
if (viz[highestNode[newNode]] < viz[highestNode[node]])
highestNode[node] = highestNode[newNode];
if (highestNode[newNode] == node) {
++nrComp;
if (print > 0) {
while (stack_top > 0 && nodes_stack[stack_top] != newNode) {
fout << nodes_stack[stack_top] << " ";
--stack_top;
}
--stack_top;
fout << newNode << " " << node << "\n";
}
}
} else {
if (viz[newNode] < viz[highestNode[node]])
highestNode[node] = newNode;
}
}
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0, 0);
fout << nrComp << "\n";
rst(n);
dfs(1, 0, 1);
return 0;
}