Pagini recente » Cod sursa (job #483811) | Cod sursa (job #2363704) | Cod sursa (job #2970903) | Cod sursa (job #2348473) | Cod sursa (job #3041974)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int nmax = 1e5;
vector < int > g[nmax];
vector < int > c[nmax];
int comp = 0;
int vis[nmax];
struct time {
int in;
int low;
} info[nmax];
stack < int > st;
int T = 0;
void dfs ( int node, int par = -1 ) {
vis[node] = 1;
info[node].in = info[node].low = T++;
st.push ( node );
for ( int x: g[node] )
if ( x != par ) {
if ( vis[x] )
info[node].low = min ( info[node].low, info[x].in );
else {
dfs ( x, node );
info[node].low = min ( info[node].low, info[x].low );
if ( info[x].low >= info[node].in ) {
while ( st.top () != x )
c[comp].push_back ( st.top () ), st.pop ();
c[comp].push_back ( x ); st.pop ();
c[comp].push_back ( node );
comp++;
}
}
}
}
ifstream fin ( "biconex.in" );
ofstream fout ( "biconex.out" );
int main() {
int n, m, x, y;
fin >> n >> m;
for ( int i = 0; i < m; i++ ) {
fin >> x >> y;
x--, y--;
g[x].push_back ( y );
g[y].push_back ( x );
}
for ( int i = 0; i < n; i++ )
if ( ! vis[i] )
dfs ( i );
fout << comp << '\n';
for ( int i = 0; i < comp; i++, fout << '\n' )
for ( int x: c[i] )
fout << 1 + x << ' ';
return 0;
}