Cod sursa(job #1085246)

Utilizator anaid96Nasue Diana anaid96 Data 16 ianuarie 2014 21:26:01
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
//Include
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<stack>
#include<set>

using namespace std;

FILE *in,*out;

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

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

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

//variabile

int noduri,muchii,nod1,nod2;
int minlevel[Nmax],depth[Nmax];
vector<int> graph[Nmax];
stack<pii> stiva;
vector<set<int> > answer;

int main(void)
{
	in=fopen("biconex.in","rt");
	fscanf(in,"%d%d",&noduri,&muchii);
	for(int i=0;i<muchii;++i)
	{
		fscanf(in,"%d%d",&nod1,&nod2);
		graph[nod1].pb(nod2);
		graph[nod2].pb(nod1);	
	}
	dfs(1,-1,1);
	
	out=fopen("biconex.out","wt");
	
	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,end=it->end();
		for(sit=it->begin();sit!=end; ++sit)
			fprintf(out,"%d ",*sit);
		fprintf(out,"\n");
	}	
	
	fclose(in);
	fclose(out);
	return 0;
}	

void dfs(int nod,int tata,int level)
{
	minlevel[nod]=depth[nod]=level;
	vector<int> :: iterator it,end=graph[nod].end();
	for(it=graph[nod].begin() ; it!=end ; ++it)
	{
		if(*it==tata)
			continue;
		if(depth[*it])
		{
			minlevel[nod]=min(minlevel[nod],depth[*it]);
			continue;
		}	
		stiva.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=stiva.top();
		stiva.pop();
		temp.insert(curent.first);
		temp.insert(curent.second);
		
	}
	while(curent!=stop);
	answer.pb(temp);
	temp.clear();
}