Pagini recente » Cod sursa (job #1108618) | Cod sursa (job #2649025) | Cod sursa (job #682330) | Cod sursa (job #1329517) | Cod sursa (job #2954763)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );
int descop[NMAX+1];
int low[NMAX+1];
vector <int> edges[NMAX+1];
bool viz[NMAX+1];
stack <int> stiva;
int t = 0;
vector<int> biconexe[NMAX+1];
int comp = 0;
void print_bcc( int u ) {
while( stiva.top() != u ) {
biconexe[comp].push_back( stiva.top() );
stiva.pop();
}
biconexe[comp].push_back( u );
stiva.pop();
}
void dfs( int node, int parent ) {
viz[node] = true;
descop[node] = low[node] = t++;
stiva.push( node );
for( auto vec: edges[node] ) {
if( !viz[vec] ) {
dfs( vec, node );
low[node] = min( low[node], low[vec] );
if( low[vec] >= descop[node] ) {
print_bcc( vec );
biconexe[comp].push_back( node );
comp++;
}
}
else if( vec != parent && descop[vec] < descop[node] ) {
low[node] = min( low[node], descop[vec] );
}
}
}
int main() {
int n, m, i, a, b;
fin >> n >> m;
for( i = 0; i < m; i++ ) {
fin >> a >> b;
edges[a].push_back( b );
edges[b].push_back( a );
}
for( i = 1; i <= n; i++ ) {
if( !viz[i] )
dfs( i, 0 );
}
fout << comp << "\n";
for( i = 0; i < comp; i++ ) {
for( auto elem: biconexe[i] )
fout << elem << " ";
fout << "\n";
}
return 0;
}