Pagini recente » Cod sursa (job #3233260) | Cod sursa (job #650622) | Cod sursa (job #345496) | Cod sursa (job #1497217) | Cod sursa (job #2708237)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nmax = 100000;
vector <int> g[nmax+1];
int level;
int l[nmax+1], ll[nmax+1], f[nmax+1];
stack <int> s;
vector < vector <int> > sol;
void dfs( int x ) {
++ level;
l[x] = level;
ll[x] = level;
s.push(x);
for ( int i = 0; i < int(g[x].size()); ++ i ) {
int xn = g[x][i];
if ( xn != f[x] ) {
if ( l[xn] == 0 ) {
f[xn] = x;
dfs(xn);
if ( ll[xn] < l[x] ) {
ll[x] = ll[xn];
} else {
int nsol = sol.size()+1;
sol.resize(nsol);
sol[nsol-1].resize(0);
while ( s.top() != xn ) {
sol[nsol-1].push_back(s.top());
s.pop();
}
s.pop();
sol[nsol-1].push_back(xn);
sol[nsol-1].push_back(x);
}
} else {
if ( l[xn] < ll[x] ) {
ll[x] = l[xn];
}
}
}
}
}
int main( ) {
int n, m;
fin >> n >> m;
for ( int i = 1; i <= m; ++ i ) {
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for ( int i = 1; i <= n; ++ i ) {
if ( l[i] == 0 ) {
dfs(i);
while ( s.empty() == 0 ) {
s.pop();
}
}
}
fout << sol.size() << "\n";
for ( int i = 0; i < int(sol.size()); ++ i ) {
for ( int j = 0; j < int(sol[i].size()); ++ j ) {
fout << sol[i][j] << " ";
}
fout << "\n";
}
return 0;
}