Pagini recente » Cod sursa (job #45789) | Cod sursa (job #2711525) | Cod sursa (job #690342) | Cod sursa (job #682530) | Cod sursa (job #2510715)
#include <fstream>
#include <vector>
#define N 100000 + 1
using namespace std;
ifstream f ( "biconex.in" );
ofstream g ( "biconex.out" );
vector < int > graph[N];
int lvl, vsol[N], sol[N], niv[N], low[N], st[N], k, num, critic[N];
bool stiva[N];
void dfs ( int node ){
niv[node] = low[node] = ++lvl;
st[++k] = node;
stiva[node] = 1;
for ( int i = 0; i < graph[node].size ( ); i++ ){
int new_node = graph[node][i];
if ( niv[new_node] == 0 ){
dfs ( new_node );
low[node] = min ( low[node], low[new_node] );
if ( niv[node] <= low[new_node] ){
critic[node] = new_node;
num++;
sol[num] = sol[num - 1] + 1;
vsol[sol[num]] = node;
while ( st[k] != new_node ){
vsol[++sol[num]] = st[k];
stiva[st[k]] = 0;
k--;
}
vsol[++sol[num]] = st[k];
stiva[st[k]] = 0;
k--;
}
}
else if ( stiva[new_node] == 1 )
low[node] = min ( low[node], niv[new_node] );
}
}
int main()
{ int n, m, i, x, y;
f >> n >> m;
for ( i = 1; i <= m; i++ ){
f >> x >> y;
graph[x].push_back ( y );
graph[y].push_back ( x );
}
for ( i = 1; i <= n; i++ )
if ( niv[i] == 0 )
dfs ( i );
g << num << '\n';
for ( i = 1; i <= num; i++ ){
for ( int j = sol[i - 1] + 1; j <= sol[i]; j++ )
g << vsol[j] << ' ';
g << '\n';
}
return 0;
}