Cod sursa(job #1386803)

Utilizator BLz0rDospra Cristian BLz0r Data 13 martie 2015 11:52:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

#define Nmax 100002
#define pb push_back
#define mp make_pair

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

vector < int > G[Nmax], Sol[Nmax];
stack < pair < int , int > > st;
int index = 1, idx[Nmax], lowlink[Nmax], nrs;

void AddComp ( int x ,int y ){
	int ax, ay;
	
	nrs++;
	
	do{
		ax = st.top().first;
		ay = st.top().second;
		st.pop();
		Sol[nrs].pb ( ax );
		Sol[nrs].pb ( ay );
	}while( ax != x || ay != y );
}

void GetComp ( int nod, int pred ){
	vector < int > :: iterator it;
	
	idx[nod] = lowlink[nod] = index;
	index++;
	
	for ( it = G[nod].begin(); it < G[nod].end(); ++it ){
		if ( nod == pred ) continue;
		if ( !idx[*it] ){
			st.push ( mp ( nod, *it ) );
			GetComp ( *it, nod );
			lowlink[nod] = min ( lowlink[nod], lowlink[*it] );
			
			if ( lowlink[*it] >= idx[nod] )
				AddComp ( nod, *it );
			
		}
		else
			lowlink[nod] = min ( lowlink[nod], idx[*it] );
	}
}
int main(){
	int N, M, x, y;
	vector < int > :: iterator it;
	
	fscanf ( f, "%d%d", &N, &M );
	
	for ( int i = 1; i <= M; ++i ){
		fscanf ( f, "%d%d", &x, &y );
		G[x].pb ( y );
		G[y].pb ( x );
	}
	
	for ( int i = 1; i <= N; ++i )
		if ( !idx[i] )
			GetComp ( i, 0 );
	
	fprintf ( g, "%d\n", nrs );
	
	for ( int i = 1; i <= nrs; ++i ){
		sort ( Sol[i].begin(), Sol[i].end() );
		Sol[i].erase ( unique ( Sol[i].begin(), Sol[i].end() ), Sol[i].end() );
		for ( it = Sol[i].begin(); it < Sol[i].end(); ++ it )
			fprintf ( g, "%d ", *it );
		fprintf ( g, "\n" );
	}
	
	return 0;
}