Pagini recente » Cod sursa (job #1047878) | Cod sursa (job #1875058) | Cod sursa (job #1047653) | Cod sursa (job #2150304) | Cod sursa (job #1415519)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
const int NMAX = 100000 + 1;
int n, m, nrcomp;
int index_crt;
int niv[NMAX];
vector <int> graf[NMAX], comp[NMAX];
stack <int> st;
void citeste() {
int a, b;
f >> n >> m;
for (int i = 1; i <= m; i++) {
f >> a >> b;
graf[a].push_back(b);
graf[b].push_back(a);
}
}
int DFS(int nod, int nivel, int tata) {
int h, h2;
niv[nod] = h = nivel;
st.push(nod);
int fiu, l = graf[nod].size();
for (int i = 0; i < l; i++) {
fiu = graf[nod][i];
if (fiu == tata) continue;
if (!niv[fiu]) {
h2 = DFS(fiu, nivel + 1, nod);
if (h2 >= niv[nod]) {
comp[++nrcomp].push_back(nod);
while (st.top() != nod) {
comp[nrcomp].push_back(st.top());
st.pop();
}
}
h = min(h, h2);
}
else h = min(h, niv[fiu]);
}
return h;
}
void scrie() {
int a, b;
g << nrcomp << '\n';
for (int i = 1; i <= nrcomp; i++) {
b = comp[i].size();
for (int j = 0; j < b; j++) g << comp[i][j] << ' ';
g << '\n';
}
}
int main() {
citeste();
DFS(1, 1, 0);
scrie();
}