Pagini recente » Cod sursa (job #2275054) | Cod sursa (job #358095) | Cod sursa (job #496113) | Cod sursa (job #2850380) | Cod sursa (job #849613)
Cod sursa(job #849613)
#include<stdio.h>
#include<cstring>
#include<vector>
#include<stack>
#define nmax 100001
#define MIN(a,b) a>b?b:a
using namespace std;
int N,M,nr_componente;
vector <int> G[nmax],C[nmax]; //G pentru listele de adiacenta,C pentru componente;
int niv[nmax],niv_min_acc[nmax],tata[nmax]; ///niv nivelul nodului,niv_min_acc nivelul minim accesibil,tata vectorul de tati;
int viz[nmax],aux[nmax]; //viz vectorul de vizitare,aux pentru componentele biconexe;
stack<int> stiva;
void citeste()
{
int i,x,y;
FILE *f=fopen("biconex.in","rt");
fscanf(f,"%i%i",&N,&M);
for(i=0;i<M;++i)
{
fscanf(f,"%i%i",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
fclose(f);
}
void adauga_componenta(int nod)
{
memset(aux,0,sizeof(aux));
int x;
while(stiva.top() != nod)
{
x=stiva.top();
if(aux[x]==0)
C[nr_componente].push_back(x);
aux[x]=1;
stiva.pop();
}
if(aux[stiva.top()]==0)
C[nr_componente].push_back(stiva.top());
++nr_componente;
}
void df(int nod,int nivel)
{
viz[nod]=1;
niv_min_acc[nod]=nivel;
niv[nod]=nivel;
stiva.push(nod);
for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();++it)
{
int x=*it;
if(viz[x]==0)
{
stiva.push(nod); //adaugam in stiva;
tata[x]=nod; //actualizam vectorul de tati;
df(x,nivel + 1); //facem o parcurgere si din nodul fiu x;
niv_min_acc[nod]=MIN(niv_min_acc[nod],niv_min_acc[x]); //nivelul minim accesibil este minimul dintre nivelul minim accesibil al sau si al tuturor fiilor
if(niv_min_acc[x]>=niv[nod]) //atunci "nod" este nod critic si va incepe o noua componenta biconexa
adauga_componenta(nod);
}
else if(tata[nod]!=x) //muchie de intoarcere
niv_min_acc[nod]=MIN(niv[x],niv_min_acc[nod]);
}
}
void afiseaza()
{
FILE *g=fopen("biconex.out","wt");
fprintf(g,"%i\n",nr_componente);
for(int i=0;i<nr_componente;++i)
{
for(vector<int>::iterator it=C[i].begin();it!=C[i].end();++it)
fprintf(g,"%i ",*it);
fprintf(g,"\n");
}
fclose(g);
}
int main()
{
citeste();
int i;
for(i=1;i<=N;++i)
if(viz[i]==0)
df(i,1);
afiseaza();
return 0;
}