Pagini recente » Cod sursa (job #179853) | Cod sursa (job #1482272) | Cod sursa (job #3210046) | Cod sursa (job #2951298) | Cod sursa (job #1831279)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
#define DIM 100005
vector <vector <int> > G, Rez;
int tmp = 1, N, M, x, y;
int Timp[DIM], Best[DIM], viz[DIM], St[DIM], eSt[DIM];
void DF(int nod, int prev);
int main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d\n", &N, &M);
G.resize(N + 2);
for(int i = 1; i <= M; ++i) {
scanf("%d %d\n", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for(int i = 1; i <= N; ++i) {
if(!viz[i]) {
DF(i, 0);
}
}
cout << Rez.size() << '\n';
for(unsigned int c = 0; c < Rez.size(); ++c) {
for(unsigned int z = 0; z < Rez[c].size(); ++z) {
cout << Rez[c][z] << ' ';
}
cout << '\n';
}
return 0;
}
void DF(int nod, int prev) {
viz[nod] = 1;
St[++St[0]] = nod;
eSt[nod] = 1;
Timp[nod] = tmp;
Best[nod] = tmp++;
for(unsigned int z = 0; z < G[nod].size(); ++z) {
if(prev == G[nod][z]) continue;
if(!viz[G[nod][z]]) {
DF(G[nod][z], nod);
if(Best[G[nod][z]] == Timp[G[nod][z]]) {
vector <int> x;
x.push_back(nod);
x.push_back(G[nod][z]);
Rez.push_back(x);
}
if(Timp[nod] == Best[G[nod][z]]) {
vector <int> x;
while(St[St[0]] != nod) {
x.push_back(St[St[0]]);
eSt[St[St[0]]] = 0;
--St[0];
}
x.push_back(nod);
Rez.push_back(x);
// eSt[nod] = 0;
// --St[0];
}
Best[nod] = min(Best[nod], Best[G[nod][z]]);
}
else {
if(eSt[G[nod][z]] == 1) {
Best[nod] = min(Best[nod], Best[G[nod][z]]);
}
}
}
if(Best[nod] == Timp[nod]) {
// vector <int> x;
//
// while(St[St[0]] != nod) {
// x.push_back(St[St[0]]);
// eSt[St[St[0]]] = 0;
// --St[0];
// }
//
// x.push_back(nod);
//
// Rez.push_back(x);
//
// eSt[nod] = 0;
// --St[0];
// }
--St[0];
eSt[nod] = 0;
}
}