Cod sursa(job #1088305)

Utilizator anaid96Nasue Diana anaid96 Data 20 ianuarie 2014 14:27:03
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
#include<stack>

using namespace std;

FILE *in,*out;

//definitii
#define pb push_back
#define mp make_pair
#define pii pair<int,int>

//functii
void dfs(int nod,int tata,int level);
void biconex(pii stop);

//constante
const int Nmax=(int) 1e5+1;

//variabile
int noduri,muchii;
int nod1,nod2;
int minlevel[Nmax];
vector<int> graf[Nmax];
stack<pii > st;
vector<set<int> > answer;

int main(void)
{
	in=fopen("biconex.in","rt");
	out=fopen("biconex.out","wt");
	fscanf(in,"%d%d",&noduri,&muchii);
	for(int i=1;i<=muchii;++i)
	{	
		fscanf(in,"%d%d",&nod1,&nod2);
		graf[nod1].pb(nod2);
		graf[nod2].pb(nod1);
	}	
	dfs(1,-1,1);
	
	fprintf(out,"%d\n",answer.size());
	vector<set<int> > :: iterator it,end=answer.end();
	for(it=answer.begin() ; it!=end ; ++it)
	{
		set<int> :: iterator sit,send=it->end();
		for(sit=it->begin() ; sit!=send ; ++sit)
			fprintf(out,"%d ",*sit);
		fprintf(out,"\n");
	}	
	
	fclose(in);
	fclose(out);
	return 0;
	
}	

void dfs(int nod,int tata,int level)
{
	minlevel[nod]=level;
	vector<int> :: iterator it,end=graf[nod].end();
	for(it=graf[nod].begin() ; it!=end ; ++it)
	{
		if(*it==tata)
			continue;
		if(minlevel[*it])
		{
			minlevel[nod]=min(minlevel[nod],minlevel[*it]);
			continue;
		}	
		st.push(mp(nod,*it));
		
		dfs(*it,nod,level+1);
		
		minlevel[nod]=min(minlevel[nod],minlevel[*it]);
		if(level<=minlevel[*it])
			biconex(mp(nod,*it));
	}	
}

void biconex(pii stop)
{
	set<int> temp;
	pii curent;
	do
	{
		curent=st.top();
		st.pop();
		temp.insert(curent.first);
		temp.insert(curent.second);
	}	
	while(curent!=stop);
	answer.pb(temp);
	temp.clear();
	
}