Pagini recente » Cod sursa (job #861807) | Cod sursa (job #2732009) | Cod sursa (job #2400608) | Cod sursa (job #2623408) | Cod sursa (job #1165273)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define FILEIN "biconex.in"
#define FILEOUT "biconex.out"
#define NMAX 100005
#define MMAX 200005
vector<int> A[NMAX];
int N, M;
int Depth[NMAX], Low[NMAX];
stack<pair<int, int> > St;
vector<vector<int> > Sol;
void AddSol(int fx, int fy) {
vector<int> Biconex;
int x, y;
do {
x = St.top().first, y = St.top().second, St.pop();
Biconex.push_back(x);
Biconex.push_back(y);
} while ( x != fx && y != fy );
sort(Biconex.begin(), Biconex.end());
Biconex.erase(unique(Biconex.begin(), Biconex.end()), Biconex.end());
Sol.push_back(Biconex);
}
void DF(int nod, int parent, int depth) {
Depth[nod] = depth;
Low[nod] = depth;
for (int i = 0; i < A[nod].size(); i++ ) {
int y = A[nod][i];
if ( y == parent ) continue;
if ( Depth[y] == 0 ) {
St.push(make_pair(nod, y));
DF(y, nod, depth+1);
Low[nod] = min(Low[nod], Low[y]);
if (Low[y] >= Depth[nod]) {
// nod = nod articulatie => comp biconexa
AddSol(nod, y);
}
} else {
Low[nod] = min(Low[nod], Depth[y]);
}
}
}
int main() {
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
scanf("%d %d", &N, &M);
for ( int i = 1, x, y; i <= M; i++ ) {
scanf("%d %d", &x, &y);
A[x].push_back(y), A[y].push_back(x);
}
for ( int i = 1; i <= N; i++ ) {
if (Depth[i] == 0)
DF(i, 0, 1);
}
printf("%d\n", Sol.size());
for ( int i = 0; i < Sol.size(); i++ ) {
for ( int j = 0; j < Sol[i].size(); j++ ) {
printf("%d ", Sol[i][j]);
}
printf("\n");
}
return 0;
}