Cod sursa(job #613297)

Utilizator balakraz94abcd efgh balakraz94 Data 20 septembrie 2011 21:42:52
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#include<stack>
#define infile "biconex.in"
#define outfile "biconex.out"
#define n_max 100005
#define min(x,y) x<y ? x : y
#define pb push_back
#define mkp make_pair
using namespace std;

void citeste();
void rezolva();
void afiseaza();


vector < int > v[n_max];//graful

stack < pair<int, int> > st;//stiva

vector < vector < int> > sol;//solutia

int dfn[n_max], low[n_max];

int n,m, nrsol;


void citeste()
{
	freopen(infile,"r",stdin);
	
	int x,y;
	
	scanf("%d %d",&n,&m);
	
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		
		v[x].pb(y);
		v[y].pb(x);
	}
	
	fclose(stdin);
}



void extrage(int x, int y)
{
	pair < int, int> muchie;
	
	vector< int > aux;
	
	do
	{
		muchie = st.top();
		st.pop();
		aux.pb(muchie.first);
		aux.pb(muchie.second);
	} while(muchie.first !=x || muchie.second !=y);
	
	sort(aux.begin(), aux.end());//sortez
	
	aux.erase( unique(aux.begin(),aux.end()), aux.end() );//elimin duplicatele consecutive
	
	sol.pb(aux);//adaug componenta biconexa
	
	nrsol++;
}




void df(int x, int t, int h)
{
	dfn[x] = h;
	low[x] = h;
	
	int nodc;
	vector < int > ::iterator it;
	
	for(it = v[x].begin(); it!=v[x].end(); ++it)
	{
		nodc = *it;
		
		if(nodc!=t)
		{
			if(!dfn[nodc])//muchie din arbore
			{
				st.push(mkp(x,nodc));
				
				df(nodc,x,h+1);
				
				low[x] = min(low[x],low[nodc]);
				
				if(dfn[x] <= low[nodc])//nodc este punct de articulatie
					extrage(x,nodc);
			}
			else if(dfn[x] > dfn[nodc])//muchie de intoarcere
			{
				st.push(mkp(x,nodc));
				
				low[x] = min(low[x],low[nodc]);
			}
		}
	}
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",nrsol);
	
	for(unsigned int i=0;i<sol.size();++i)
	{
		for(unsigned int j=0; j<sol[i].size(); ++j)
			printf("%d ",sol[i][j]);
	
	printf("\n");
	}
	
	fclose(stdout);
}


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