Pagini recente » Cod sursa (job #1773710) | Cod sursa (job #2669215) | Cod sursa (job #2763433) | Cod sursa (job #2713754) | Cod sursa (job #852357)
Cod sursa(job #852357)
/*
* =====================================================================================
*
* 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;
}