Cod sursa(job #614326)

Utilizator balakraz94abcd efgh balakraz94 Data 5 octombrie 2011 23:30:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include<fstream>
#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;


void citeste()
{
	ifstream fin(infile);
	
	int x,y;
	
	fin>>n>>m;
	
	for(int i=1;i<=m;i++)
	{
		fin>>x>>y;
		
		v[x].pb(y);
		v[y].pb(x);
	}
	
	fin.close();
}



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);
	
	sol.pb(aux);//adaug componenta biconexa
}




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()
{
	ofstream fout(outfile);
	
	fout<<sol.size()<<'\n';
	
	for(unsigned int i=0;i<sol.size();++i)
	{
		sort(sol[i].begin(),sol[i].end());
		
		int ant = -1;
		
		for(unsigned int j=0; j<sol[i].size(); ++j)
			if(sol[i][j]!=ant)
			{
				fout<<sol[i][j]<<" ";
			    ant = sol[i][j];
			}
	
		fout<<'\n';
	}
	
	fout.close();
}


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