Cod sursa(job #960045)

Utilizator lucky1992Ion Ion lucky1992 Data 9 iunie 2013 17:51:08
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <stack>
#include <fstream>
#include <iostream>

#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] ){
				
					muchie m;
					vector<int> isIn( NMAX, 0 );
					++t;
					fprintf(stderr,"%d\n",t+1);
					do{
						m  = s.top();
						s.pop();
						
						if( isIn[m.first] == 0 )
						components[t].push_back( m.first );
						isIn[m.first] = 1;
						
						if( isIn[m.second] == 0 )
						components[t].push_back( m.second );
						isIn[m.second] = 1;
						
						inStack[m.first] = 0;
						inStack[m.second] = 0;
						
					}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++){
			for( unsigned k = 0; k < components[i].size(); k++ )
				printf("%d ", components[i][k]);
			printf("\n");
		}
		

		return 0;
}