Pagini recente » Cod sursa (job #2709093) | Cod sursa (job #1834718) | Cod sursa (job #1610174) | Cod sursa (job #78569) | Cod sursa (job #596484)
Cod sursa(job #596484)
#include<fstream>
#include<cstdlib>
using namespace std;
int n,m,start=1;
int *A[100010];
int dfn[100010],low[100010];
// dfn[x]=numarul de ordine al nodului x in parcurgerea DFS a grafului
// low[x]=numarul de ordine al primului nod din parcurgerea DFS ce poate fi atins din x
// pe un alt lant decat lantul unic din arborele partial DFS
// low[x]=min{dfn[x] , min{low[y] | y fiu al lui x} , min{dfn[y] | [x,y] muchie de intoarcere}}
int num,nrfii,vf,nrc;
// num - folosita la calcularea numarului de ordine a nodului curent in parcurgerea DFS
// nrfii = numarul de fii ai nodului start
// nrc = numarul de componente biconexe
struct Muchie{int x,y;};
Muchie S[200010];
int *com[100010]; //lista componentelor biconexe
bool afisat[100010];
void Citire()
{
int i,x,y;
ifstream fin("biconex.in");
fin>>n>>m;
for(i=1;i<=n;i++)
{
A[i]=(int *)realloc(A[i],sizeof(int));
A[i][0]=0;
}
for(i=1;i<=m;i++)
{
fin>>x>>y;
A[x][0]++;
A[x]=(int *)realloc(A[x],(A[x][0]+1)*sizeof(int));
A[x][A[x][0]]=y;
A[y][0]++;
A[y]=(int *)realloc(A[y],(A[y][0]+1)*sizeof(int));
A[y][A[y][0]]=x;
}
fin.close();
}
void Initializare()
{
int i;
for(i=1;i<=n;i++)
{
com[i]=(int *)realloc(com[i],sizeof(int));
com[i][0]=0;
}
for(i=1;i<=n;i++)
dfn[i]=low[i]=-1;
vf=0;
//initializez stiva cu o muchie fictiva intre nodul de start si un nod fictiv -1
S[vf].x=start;
S[vf].y=-1;
}
void DeterminareComponentaBiconexa(int u,int x)
{
//determina componenta biconexa a muchiei [u,x]
Muchie p;
nrc++; //incrementez numarul componentelor biconexe
do
{
p=S[vf--]; //extrag o muchie din stiva
com[nrc][0]++;
com[nrc]=(int *)realloc(com[nrc],(com[nrc][0]+1)*sizeof(int));
com[nrc][com[nrc][0]]=p.x;
}
while(!(p.x==u && p.y==x)); //cat timp nu gasesc muchia [u,x]
if(com[nrc][0]==1)
{
com[nrc][0]++;
com[nrc]=(int *)realloc(com[nrc],(com[nrc][0]+1)*sizeof(int));
com[nrc][com[nrc][0]]=p.y;
}
}
void Biconex(int u,int tu)
{
// u este nodul curent , iar tu este nodul parinte al lui u
int x,i;
num++;
dfn[u]=low[u]=num; //low[u] este si el initial numarul de ordine al lui u
//parcurg lista de adiacenta a nodului u
for(i=1;i<=A[u][0];i++)
{
x=A[u][i]; //x este nod adiacent cu u
if(x!=tu && dfn[x]<dfn[u])
{
//inserez muchia [u,x] in stiva
vf++;
S[vf].x=x;
S[vf].y=u;
}
if(dfn[x]==-1) //nodul x nu a mai fost vizitat
{
if(u==start) //am gasit un fiu al nodului start
nrfii++;
Biconex(x,u);
low[u]=min(low[u],low[x]);
if(low[x]>=dfn[u]) //nodul u este punct de articulatie
{
//am gasit o componenta biconexa
//formata din muchiile din stiva pana la intalnirea muchiei [u,x]
DeterminareComponentaBiconexa(x,u);
}
}
else //nodul x a mai fost vizitat
{
if(x!=tu) //daca x nu este tatal lui u
{
//atunci [u,x] este muchie de intoarcere de la u la x
low[u]=min(low[u],dfn[x]);
}
}
}
}
int main()
{
int i,j,ultim,prim;
Citire();
Initializare();
Biconex(start,-1);
ofstream fout("biconex.out");
fout<<nrc<<"\n";
for(i=1;i<=nrc;i++)
{
fout<<com[i][1]<<' ';
prim=com[i][1];
if(com[i][0]==2)
{
fout<<com[i][2]<<' ';
}
else
{
if(com[i][2]!=prim)
{
fout<<com[i][2]<<' ';
ultim=com[i][2];
}
else
ultim=prim;
j=3;
for(;j<=com[i][0];j++)
{
if(com[i][j]!=ultim && com[i][j]!=prim && com[i][j]!=com[i][2])
{
fout<<com[i][j]<<' ';
ultim=com[i][j];
}
}
}
fout<<"\n";
}
fout.close();
return 0;
}