Pagini recente » Cod sursa (job #1942400) | Cod sursa (job #630356) | Cod sursa (job #723795) | Cod sursa (job #1949906) | Cod sursa (job #2199447)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define dMAX 100000
using namespace std;
int n, m, x, y, idx;
vector<int> graf[dMAX + 2];
vector<int> cBiconexe[dMAX + 2];
stack<int> vBiconexe;
bool viz[dMAX + 2];
int level[dMAX + 2], nma[dMAX + 2];
ifstream fin("biconex.in");
ofstream fout("biconex.out");
void DFS(int v, int pv) {
viz[v] = true;
vBiconexe.push(v);
level[v] = level[pv] + 1;
nma[v] = level[v];
int newV, u;
for (u = 0; u < graf[v].size(); u++) {
newV = graf[v][u];
if (!viz[newV]) {
DFS(newV, v);
nma[v] = min(nma[v], nma[newV]);
if (level[v] <= nma[newV]) {
idx++;
while (vBiconexe.top() != newV && !vBiconexe.empty()) {
cBiconexe[idx].push_back(vBiconexe.top());
vBiconexe.pop();
}
cBiconexe[idx].push_back(newV);
if (!vBiconexe.empty())
vBiconexe.pop();
cBiconexe[idx].push_back(v);
sort(cBiconexe[idx].begin(), cBiconexe[idx].end());
}
} else {
if (newV != pv) {
nma[v] = min(nma[v], level[newV]);
}
}
}
}
int main()
{
int i, j;
fin >> n >> m;
for (i = 1; i <= m; i++) {
fin >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
DFS(1, 0);
fout << idx << '\n';
for (i = 1; i <= idx; i++) {
for (j = 0; j < cBiconexe[i].size(); j++) {
fout << cBiconexe[i][j] << ' ';
}
fout << '\n';
}
return 0;
}