Pagini recente » Cod sursa (job #286705) | Cod sursa (job #3207517) | Cod sursa (job #1173996) | Cod sursa (job #1098098) | Cod sursa (job #1765716)
#include<fstream>
#include<vector>
#include<stack>
using namespace std;
ifstream fin ("biconex.in"); ofstream fout ("biconex.out");
typedef vector< int > graf;
const int nmax = 1e5;
const int inf = (1 << 30) - 1 + (1 << 30);
int h[nmax + 1], d[nmax + 1];
graf g[nmax + 1];
stack< pair<int, int> > st;
vector< vector< int > > sol;
inline int min2 (int a, int b) {
return (a < b ? a : b);
}
void scoate (pair<int, int> c) {
vector< int > aux;
while (!st.empty() && st.top() != c) {
aux.push_back(st.top().second);
st.pop();
}
aux.push_back( c.second );
aux.push_back( c.first );
st.pop();
sol.push_back( aux );
}
void dfs (int nod, int tata) {
for (auto it : g[ nod ]) {
if (it != tata) {
if (h[ it ] == inf) {
h[ it ] = h[ nod ] + 1;
st.push( make_pair(nod, it) );
dfs(it, nod);
d[ nod ] = min2(d[ nod ], d[ it ]);
if (d[ it ] >= h[ nod ]) {
scoate( make_pair(nod, it) );
}
} else {
d[ nod ] = min2(d[ nod ], h[ it ]);
}
}
}
}
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) {
h[ i ] = d[ i ] = inf;
}
h[ 1 ] = 1;
dfs(1, 0);
fout << (int)sol.size() << "\n";
for (auto it : sol) {
for (auto it2 : it) {
fout << it2 << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}