Pagini recente » Cod sursa (job #2851101) | Cod sursa (job #3032229) | Cod sursa (job #3249457) | Cod sursa (job #2905297) | Cod sursa (job #852405)
Cod sursa(job #852405)
#include<fstream>
#include<cstring>
#include<vector>
#include<stack>
using namespace std;
#define nmax 100001
#define MIN(a,b) a>b?b:a
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 adauga_componenta(int nod)
{
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]);
}
}
int main()
{
//citire
int x,y;
ifstream fin ("biconex.in");
fin>>N>>M;
for(int i=0;i<M;++i)
{
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
fin.close();
//apelare
for(int i=1;i<=N;++i)
if(viz[i]==0)
df(i,1);
//scriere
ofstream fout("biconex.out");
fout<<nr_componente<<'\n';
for(int i=0;i<nr_componente;++i)
{
for(vector<int>::iterator it=C[i].begin();it!=C[i].end();++it)
fout<<*it<<' ';
fout<<'\n';
}
fout.close();
return 0;
}