Pagini recente » Cod sursa (job #2514080) | Cod sursa (job #686511) | Cod sursa (job #1166426) | Cod sursa (job #2100260) | Cod sursa (job #2370685)
#include <fstream>
#include <vector>
#include<stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nMax = 100000;
const int oo = 200000000;
int n, m;
vector<int> g[nMax + 5];
vector<vector<int>> sol;
stack<int> st;
int low[nMax + 5], niv[nMax + 5];
int use[nMax + 5];
void Add(int tt, int fiu) {
vector<int> step;
while (st.top() != fiu) {
step.push_back(st.top());
st.pop();
}
step.push_back(fiu);
step.push_back(tt);
st.pop();
sol.push_back(step);
}
void DFS(int nod, int tt) {
use[nod] = 1;
for (auto i : g[nod]) {
if (i == tt)
continue;
if (use[i] == 1)
low[nod] = min(low[nod], niv[i]);
else {
st.push(i);
niv[i] = niv[nod] + 1;
DFS(i, nod);
low[nod] = min(low[nod], low[i]);
if (low[i] >= niv[nod])
Add(nod, i);
}
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= n; i++) {
low[i] = oo;
}
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (use[i] == 0)
DFS(i, 0);
fout << sol.size() << '\n';
for (int i = 0; i <sol.size(); i++) {
for (auto j : sol[i])
fout << j << " ";
fout << '\n';
}
}