Cod sursa(job #1550414)

Utilizator jimcarterJim Carter jimcarter Data 13 decembrie 2015 17:58:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

FILE *in = fopen ( "biconex.in" , "r" ) , *out = fopen ( "biconex.out" , "w" );

const int VMAX = 100005;
int i , j , vSize , eSize , dep [ VMAX ] , low [ VMAX ] , u , v;
vector < int > g [ VMAX ];
vector < vector < int > > cutG;
stack < pair < int , int > > comp;

void read()
{
	fscanf ( in , "%d %d\n" , &vSize , &eSize );
	for ( i = 0 ; i < eSize ; i ++ )
	{
		fscanf ( in , "%d %d\n" , &u , &v );
		g [ u ] . push_back ( v );
		g [ v ] . push_back ( u );
	}
}

void cache( int u , int v )
{
	vector < int > aux; int tx , ty;
	do {
		tx = comp . top() . first , ty = comp . top() . second;
		comp . pop();
		aux . push_back ( tx ) , aux . push_back ( ty );
	} while ( tx != u || ty != v );
	cutG . push_back ( aux );
}

void dfs ( int curNode , int prevNode , int depth )
{
	dep [ curNode ] = low [ curNode ] = depth;

	for ( int i = 0 ; i < g [ curNode ] . size() ; i ++ )
	{
		int newNode = g [ curNode ] [ i ];
		if ( newNode == prevNode ) continue;

		if ( dep [ newNode ] != 0 ) low [ curNode ] = min ( low [ curNode ] , dep [ newNode ] ); //already explored
		else //new one
		{
		    //push it onto the stack
		    comp . push ( make_pair( curNode , newNode ) );

			dfs ( newNode , curNode , depth + 1 );
			low [ curNode ] = min ( low [ curNode ] , low [ newNode ] );
			if ( low [ newNode ] >= dep [ curNode ] )
				cache ( curNode , newNode );

		}
	}
}

void cutGraph() { dfs ( 1 , 0 , 1 ); } //current node, previous node and the depth of the current node

void print()
{
	fprintf ( out , "%d\n" , cutG . size() );
	for ( i = 0 ; i < cutG . size() ; i ++ )
	{
		sort ( cutG [ i ] . begin() , cutG [ i ] . end() );
		cutG [ i ] . erase ( unique ( cutG [ i ] . begin() , cutG [ i ] . end() ) , cutG [ i ] . end() );
		for ( j = 0 ; j < cutG [ i ] . size() ; j ++ )
			fprintf ( out , "%d " , cutG [ i ] [ j ] );
		fprintf ( out , "\n" );
	}
}

int main()
{
	read();
	cutGraph();
	print();
	return 0;
}