Cod sursa(job #852357)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 11 ianuarie 2013 03:47:24
Problema Componente biconexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 3.55 kb
/*
 * =====================================================================================
 *
 *       Filename:  biconexe.cpp
 *
 *    Description:  https://infoarena.ro/problema/biconex
 *
 *        Version:  1.0
 *        Created:  01/11/2013 02:39:07 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<stdlib.h>
#include<string.h>

#define min(a,b) (a<b)?(a):(b)

using namespace std;

class GrafNeorientat
{
protected:
	int N,M;
	FILE *in,*out;
	vector<int> a[100001];            // lista de adiacenta a varfurilor
public:
	GrafNeorientat(char*,char*);
	~GrafNeorientat();
};

GrafNeorientat::GrafNeorientat(char* input,char* output)
{
	in = fopen(input,"r");
	out = fopen(output,"w");
	fscanf(in,"%d %d",&N,&M);
	int x,y;
	for(int i = 0 ; i < M ; i++)
	{
		fscanf(in,"%d %d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
}

GrafNeorientat::~GrafNeorientat()
{
	fclose(in);
	fclose(out);
}


class ComponenteBiconexe : public GrafNeorientat
{
	int componente;                   // numarul de componente biconexe
	vector<int> v[100001];              // v[i] = lista varfurilor din cea dea i-a componenta biconexa
	stack<int> s;
	typedef int* PINT;                              // nivel[i] = nivelul nodului i,viz[i]=1/0 daca vf i a fost sau nu vizitat
	PINT nivel,nivel_min,parent,viz,viz2;                 // parent[i] = tatal nodului i  , viz2[i]= la fel,doar ca pentru pentru comp biconexe
public:                                                  	// nivel_min[i] = nivelul minim accesibil al nodului i
	ComponenteBiconexe(char*,char*);
	void df(int,int);
	void addComponentaBiconexa(int);
	void solve();
	void print();
	~ComponenteBiconexe();
};

ComponenteBiconexe::ComponenteBiconexe(char* input,char* output) : GrafNeorientat(input,output)
{
	componente = 0;
	nivel = new int[100001];
	nivel_min = new int[100001];
	parent = new int[100001];
	viz = new int[100001];
	viz2 = (int*)malloc(100001*sizeof(int));
}

ComponenteBiconexe::~ComponenteBiconexe()
{
	delete [] nivel;
	delete [] nivel_min;
	delete [] parent;
	delete [] viz;
	free(viz2);
}

void ComponenteBiconexe::df(int vf,int level)
{
	viz[vf] = 1;
	nivel[vf] = level;
	nivel_min[vf] = level;
	s.push(vf);
	for(int i = 0 ; i < a[vf].size() ; i++)
	{
		int primul = a[vf][i];
		if(viz[primul] == 0)
		{
			s.push(vf);
			parent[primul] = vf;
			df(primul,level+1);        
			nivel_min[primul] = min(nivel_min[primul],nivel_min[vf]);
			if(nivel_min[primul] >= nivel[vf])
				addComponentaBiconexa(vf);
		}
		else
			if(parent[vf] != primul)
				nivel_min[vf] = min(nivel[primul],nivel_min[vf]);
	}
}

void ComponenteBiconexe::addComponentaBiconexa(int vf)
{
	int primul;
	memset(viz2,0,sizeof(viz2));
	while(s.top() != vf)
	{
		primul = s.top();
		if(viz2[primul] == 0)
			v[componente].push_back(primul);
		viz2[primul] = 1;
		s.pop();
	}
	if(viz2[s.top()] == 0)
		v[componente].push_back(s.top());
	componente++;
}

void ComponenteBiconexe::solve()
{
	for(int i = 0 ; i <= N ; i++)
		if( viz[i] == 0 )
			df(i,1);
}

void ComponenteBiconexe::print()
{
	fprintf(out,"%d\n",componente);
	for(int i = 0 ; i < componente ; i++)
	{
		for(int j = 0 ; j < v[i].size() ; j++)
			fprintf(out,"%d ",v[i][j]);
		fprintf(out,"\n");
	}
}



int main()
{
	char* file1 = "biconex.in";
	char* file2 = "biconex.out";
	ComponenteBiconexe* b;
	b = new ComponenteBiconexe(file1,file2);
	b->solve();
	b->print();
	delete b;
	return 0;
}