Pagini recente » Cod sursa (job #2252122) | Cod sursa (job #3254605) | Cod sursa (job #1219923) | Cod sursa (job #261893) | Cod sursa (job #2113503)
#include <bits/stdc++.h>
#define se second
#define fi first
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
const int Dim = 1e5 + 5;
int niv[ Dim ], mn[ Dim ];
int n, m, sz, x, y;
bool use[ Dim ];
vector <int> G[ Dim ], sol[ Dim ];
stack <pair <int, int> > stk;
void add_sol ( int node1, int node2 ) {
++sz;
while ( stk.size() != 0 && (stk.top().fi != node1 || stk.top().se != node2)) {
sol[ sz ].push_back ( stk.top().fi );
sol[ sz ].push_back ( stk.top().se );
stk.pop();
}
if ( stk.size() ) {
sol[ sz ].push_back ( stk.top().fi );
sol[ sz ].push_back ( stk.top().se );
stk.pop();
}
}
void dfs (int node, int tata, int nivel) {
niv[ node ] = mn[ node ] = nivel;
use[ node ] = 1;
for (vector <int> :: iterator it = G[ node ].begin(); it != G[ node ].end(); ++ it) {
if (use[ *it ] == 0) {
stk.push ({node, *it});
dfs ( *it, node, nivel + 1);
mn[ node ] = min ( mn[ node ], mn[ *it ]);
if ( mn[ *it ] >= niv[ node ]) {
add_sol (node, *it);
}
}
else {
mn[ node ] = min ( mn[ node ], niv[ *it ]);
}
}
}
void afis ( ) {
g << sz << '\n';
for (int i = 1; i <= sz; ++ i) {
sort (sol[ i ].begin(), sol[ i ].end());
int lst = 0;
for (vector <int> :: iterator it = sol[ i ].begin(); it != sol[ i ].end(); ++ it) {
if ( *it != lst) {
g << *it << " ";
lst = *it;
}
}
g << '\n';
}
}
int main() {
f >> n >> m;
for (int i = 1; i <= m; ++ i) {
f >> x >> y;
G[ x ].push_back ( y );
G[ y ].push_back ( x );
}
dfs (1, 0, 0);
afis ( );
return 0;
}