Pagini recente » Cod sursa (job #1899700) | Cod sursa (job #256646) | Cod sursa (job #120538) | Cod sursa (job #181995) | Cod sursa (job #3148356)
#include <bits/stdc++.h>
#define NMAX 100100
#define MMAX 200100
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n; //numarul de varfuri din graf
int start=1; //varful de start in parcurgerea DFS
int num; //numarul de ordine al varfului curent in parcurgerea DFS
int nrfii; //numarul de fii ai varfului de start
int nr; //numarul de componente biconexe
vector<int> G[NMAX]; //reprezentarea grafului prin liste de adiacenta
int dfn[NMAX], low[NMAX];
bool Art[NMAX]; //vectorul caracteristic al multimii punctelor de articulatie
struct Muchie {int f, t;};
stack<Muchie> S;
vector<int> B[MMAX]; //componentele biconexe
void Citire();
void Biconex(int ,int );
void Initializare();
void Comp_Biconexa(int, int);
void Scrie(int);
int main()
{int i;
Citire();
Initializare();
Biconex(start,-1);
//Afisez punctele de articulatie
fout<<nr<<'\n';
for (i=1; i<=nr; i++)
Scrie(i);
return 0;
}
void Citire()
{int x, y, m, i;
fin>>n>>m;
for (i=0; i<m; i++)
{fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Initializare()
{int i;
for (i=1; i<=n; i++) dfn[i]=low[i]=-1;
Muchie fictiv={start, -1};
S.push(fictiv);
}
void Biconex(int u, int tu)
//u este nodul curent; tu este nodul parinte al lui u
{int x, p;
Muchie m;
dfn[u]=low[u]=++num;
//parcurg lista de adiacenta G nodului u
for (p=0; p<G[u].size(); p++)
{x=G[u][p]; //x este un nod adiacent cu u
if (x!=tu && dfn[x]<dfn[u])
//insereaza in stiva S muchia [u,x]
{m.f=x; m.t=u; S.push(m); }
if (dfn[x]==-1) //x nu G mai fost vizitat
{if (u==start) //am gasit un fiu al varfului start
nrfii++;
Biconex(x,u);
low[u]=min(low[u],low[x]);
if (low[x]>=dfn[u]) //u este punct de articulatie
//am identificat o componenta biconexa,
//formata din muchiile din stiva S pana la
//intalnirea muchiei [u,x]
{ if (u!=start) Art[u]=1;
Comp_Biconexa(x, u); }
}
else //x a mai fost vizitat
if (x!=tu)
//x nu este tatal lui u,
//deci [u,x] e muchie de intoarcere la u la x
low[u]=min(low[u],dfn[x]);
}
}
void Comp_Biconexa(int x, int u)
//afiseaza componenta biconexa G muchiei [x,u]
{Muchie p;
nr++; //incrementez numarul de componente Biconexe
do
{p=S.top(); S.pop(); //extrag o muchie din stiva
B[nr].push_back(p.f);
B[nr].push_back(p.t);
}
while (p.t!=u || p.f!=x);
}
void Scrie(int i)
//afisam varfurile din componenta biconexa i
{int j, prec;
sort(B[i].begin(), B[i].end());
fout<<B[i][0];
prec=B[i][0];
for (j=1; j<B[i].size(); j++)
if (B[i][j]!= prec)
{fout<<' '<<B[i][j]; prec=B[i][j];}
fout<<'\n';
}