Pagini recente » Cod sursa (job #334148) | Cod sursa (job #1177306) | Cod sursa (job #2747749) | Cod sursa (job #90) | Cod sursa (job #1576068)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 1e5 + 1;
int N, M, root, cnt;
vector<int> v[NMAX]; // graf
vector<vector<int> > biconexe;
vector<int> c;
stack<pair<int, int> > s;
bool viz[NMAX];
int L[NMAX], niv[NMAX];
void dfs(int nod, int tata) {
L[nod] = niv[nod] = niv[tata] + 1;
viz[nod] = 1;
int x1, x2;
for (const int& x: v[nod]) {
if (x == tata) // sarim peste tata
continue;
if (!viz[x]) { // muchie de arbore
s.push({nod, x});
dfs(x, nod);
L[nod] = min(L[nod], L[x]);
if (L[x] >= niv[nod]) {
c.clear();
do {
x1 = s.top().first;
x2 = s.top().second;
s.pop();
c.push_back(x1);
c.push_back(x2);
} while(x1 != nod && x2 != x);
biconexe.push_back(c);
}
}
else { // muchie de intoarcere
L[nod] = min(L[nod], niv[x]);
}
}
}
void write() {
fout << biconexe.size() << '\n';
for (auto& c: biconexe) {
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
for (const auto& x: c)
fout << x << ' ';
fout << '\n';
}
}
int main() {
fin >> N >> M;
for (int x, y; M; --M) {
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
write();
fin.close();
fout.close();
return 0;
}