Pagini recente » Cod sursa (job #2297746) | Cod sursa (job #1584400) | Cod sursa (job #551389) | Cod sursa (job #2021661) | Cod sursa (job #960055)
Cod sursa(job #960055)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <stack>
#include <fstream>
#include <iostream>
#include <algorithm>
#define NMAX 100005
using namespace std;
typedef pair<int,int> muchie;
int N,M,x,y, timp = 0, t = -1;
vector<int> neigh[NMAX];
vector<int> d( NMAX, -1);
vector<int> low( NMAX, -1);
vector<int> inStack( NMAX, 0 );
vector<int> components[NMAX];
stack<muchie> s;
void explorare( int i ){
timp++;
d[i] = timp;
low[i] = timp;
for( unsigned k = 0; k < neigh[i].size(); k++ ){
if( d[ neigh[i][k] ] == -1 ){ // nu a mai fost vizitat
s.push( muchie( i, neigh[i][k] ) );
inStack[i] = 1;
inStack[ neigh[i][k] ] = 1;
explorare( neigh[i][k] );
if( low[i] > low[ neigh[i][k] ] )
low[i] = low[ neigh[i][k] ]; // extrag minimul dintre low[i] si low[neigh[i][k]]
if( low[ neigh[i][k] ] >= d[i] ){
++t;
do{
auto m = s.top();
s.pop();
components[t].push_back( m.first );
components[t].push_back( m.second );
}while( m.first != i );
}
}
else{
if( inStack[ neigh[i][k] ] == 1 ) // daca a fost vizitat si nodul e si in stiva
low[i] = ( low[i] > d[ neigh[i][k] ] ? d[neigh[i][k]] : low[i] ); // iau min dintre idx[neigh[i][k]] si b[i]
}
}
}
void dfs(){
for( int i = 1; i <= N; i++ )
if( d[i] == -1 ){ // nu a fost vizitat
explorare( i );
}
}
int main(){
freopen("biconex.in", "r", stdin );
freopen("biconex.out", "w", stdout );
scanf("%d%d",&N, &M );
for( int i = 1; i <= M ; i++ ){
scanf("%d%d",&x,&y);
neigh[x].push_back(y);
neigh[y].push_back(x);
}
dfs();
printf("%d\n", t+1);
for( int i = 0; i <= t; i++){
vector<int> &v = components[i] ;
sort( v.begin(), v.end() );
v.erase(unique(v.begin(),v.end()), v.end());
for(int &x : v) {
printf("%d ", x);
printf("\n");
}
}
return 0;
}