Cod sursa(job #694332)

Utilizator balakraz94abcd efgh balakraz94 Data 27 februarie 2012 19:54:33
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
#define infile "biconex.in"
#define outfile "biconex.out"
#define n_max 100005
#define pb push_back
#define mkp make_pair
#define pii pair <int, int>
#define it_int vector < int > ::iterator
#define nxt *it
#define FOR(g) \
    for(it_int it=g.begin(); it!=g.end(); ++it)
using namespace std;


vector < int > v[n_max];

stack < pii > ST;

vector < int > sol[n_max];

int dfn[n_max], low[n_max];

int N, M, Nrc;


void citeste()
{
	freopen(infile, "r", stdin);
	
	int x,y;
	
	scanf("%d %d", &N, &M);
	
	while(M--){
		scanf("%d %d",&x, &y);
		
		v[x].pb(y);
		v[y].pb(x);
	}
	
	fclose(stdin);
}


void extrage(int x, int y)
{
	pii edge;
	Nrc++;
	
	do{
		edge = ST.top();
		ST.pop();
		
		sol[Nrc].pb(edge.first);
		sol[Nrc].pb(edge.second);
		
	} while(edge.first !=x || edge.second !=y);
	
	sort(sol[Nrc].begin(), sol[Nrc].end());
	
	it_int it = unique(sol[Nrc].begin(), sol[Nrc].end());
	
	sol[Nrc].resize(it - sol[Nrc].begin());
}



void DFS(int x, int tx, int h)
{
	dfn[x] = h;
	low[x] = h;
	
	FOR(v[x])
		if(nxt != tx){
			if(!dfn[nxt])
			{
				ST.push(mkp(x,nxt));
				
				DFS(nxt, x, h+1);
				
				low[x] = min(low[x],low[nxt]);
				
				if(dfn[x] <= low[nxt])
					extrage(x, nxt);
			}
			else 
				if(dfn[nxt] < dfn[x]){
					ST.push(mkp(x,nxt));
					
					low[x] = min(low[x],low[nxt]);
				}
		}
}




void afiseaza()
{
	freopen(outfile, "w", stdout);
	
	printf("%d\n", Nrc);
	
	for(int i=1; i<= Nrc;++i){
		FOR(sol[i])
			printf("%d ", nxt);
		
		printf("\n");
	}
	
	fclose(stdout);
}



int main()
{
	citeste();
	
	DFS(1,0,1);
	
	afiseaza();
	
	return 0;
}