Pagini recente » Cod sursa (job #1659307) | Cod sursa (job #3197650) | Cod sursa (job #1191396) | Cod sursa (job #1860707) | Cod sursa (job #3294200)
#include <bits/stdc++.h>
#define VMAX 100005
#define INF 2000000000
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
vector<int> graf[VMAX];
int adancime[VMAX];
bool vizitat[VMAX];
bool biconex[VMAX];
vector<int> stiva,grupe_biconexe[VMAX];
int nr_grupe;
int dfs_afla_biconexe(int nod, int parinte)
{
vizitat[nod]=1;
adancime[nod]=adancime[parinte]+1;
stiva.push_back(nod);
int minim = INF;
int nr;
for(auto i:graf[nod])
{
if(vizitat[i]==0)
{
nr=dfs_afla_biconexe(i,nod);
minim=min(nr,minim);
if(nr>=adancime[nod]) // componenta biconexa
{
while(stiva.back()!=i)
{
grupe_biconexe[nr_grupe].push_back(stiva.back());
stiva.pop_back();
}
grupe_biconexe[nr_grupe].push_back(i);
stiva.pop_back();
grupe_biconexe[nr_grupe].push_back(nod);
nr_grupe++;
}
}
else if(i!=parinte)// muchie de intoarcere
{
minim = min(minim,adancime[i]);
}
}
return minim;
}
int dfs_grupe(int nod) // daca apelam dintr-un nod biconex nu mai avem cazul in care nu luam nodul initial intr-o grupa
{
vizitat[nod]=1;
stiva.push_back(nod);
for(auto i:graf[nod])
{
if(vizitat[nod]==0)
{
dfs_grupe(i);
if(biconex[nod]) // avem o grupa de biconexe
{
while(stiva.back()!=nod)
{
grupe_biconexe[nr_grupe].push_back(stiva.back());
stiva.pop_back();
}
grupe_biconexe[nr_grupe].push_back(nod);
nr_grupe++;
}
}
}
}
int main()
{
int n,m,i,j,k,t,q,nr,minim,maxim,suma;
fin>>n>>m;
for(i=0;i<m;i++)
{
fin>>j>>k;
graf[j].push_back(k);
graf[k].push_back(j);
}
dfs_afla_biconexe(1,0);
if(stiva.size()>1) // mai e o componenta neadaugata
{
while(stiva.size())
{
grupe_biconexe[nr_grupe].push_back(stiva.back());
stiva.pop_back();
}
nr_grupe++;
}
fout<<nr_grupe<<'\n';
for(i=0;i<nr_grupe;i++)
{
for(j=0;j<grupe_biconexe[i].size();j++)
fout<<grupe_biconexe[i][j]<<' ';
fout<<'\n';
}
return 0;
}