Pagini recente » Cod sursa (job #2314041) | Cod sursa (job #2672530) | Cod sursa (job #736340) | Cod sursa (job #2370353) | Cod sursa (job #2082932)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
const int NMAX = 100000 + 1;
int n, top;
int stiva[NMAX];
int nivel[NMAX];
vector <int> graf[NMAX];
vector < vector <int> > sol;
void citeste() {
int m, a, b;
f >> n >> m;
while (m--) {
f >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
}
int muchiiDeIntoarcere(int nod, int tata) {
nivel[nod] = nivel[tata] + 1;
stiva[++top] = nod;
int minim = nivel[nod];
int l = graf[nod].size();
for (int i = 0; i < l; i++) {
int fiu = graf[nod][i];
if (fiu == tata) continue;
if (nivel[fiu]) {
minim = min(minim, nivel[fiu]);
continue;
}
int x = top;
int niv = muchiiDeIntoarcere(fiu, nod);
if (niv >= nivel[nod]) {
vector <int> comp;
comp.push_back(nod);
while (top != x) {
comp.push_back(stiva[top]);
top--;
}
sol.push_back(comp);
}
minim = min(niv, minim);
}
return minim;
}
void rezolva() {
muchiiDeIntoarcere(1, 0);
}
void scrie() {
int l = sol.size();
g << l << '\n';
for (int i = 0; i < l; i++) {
int k = sol[i].size();
for (int j = 0; j < k; j++)
g << sol[i][j] << ' ';
g << '\n';
}
}
int main() {
citeste();
rezolva();
scrie();
}