Pagini recente » Cod sursa (job #2317159) | Cod sursa (job #1698895) | Cod sursa (job #1179688) | Cod sursa (job #1297384) | Cod sursa (job #868697)
Cod sursa(job #868697)
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,NIV[100001],ORD[100001],poz=1,X[100001],k;
vector<int> V[100001];//listele de adiacenta
int ns;
vector<int> S[100001];//solutia
int DF(int v,int niv)
{
if(NIV[v])
return NIV[v];//nivelul pe care e deja pus
int minlvl=niv,minn,niv2;
NIV[v] = niv;//pun nivelul
ORD[v] = poz++;//ordinea in care sunt parcurse in df
X[++k] = v;//adaug v in parcurgere
for(int i = 0;i < V[v].size(); ++i)
{
niv2 = poz;
minn = DF(V[v][i],niv+1);//parcurge incepand cu nodul adiacent
if(minn>=niv)//exista muchie de intoarcere
{
ns++;//maresc nr solutii
while(ORD[X[k]]>=niv2)//iau vb din vectorul parcurgerii df
{
S[ns].push_back(X[k]);//adaug varfurle in componenta biconexa
k--; //din parcurgerea df
}
if(S[ns].size())
S[ns].push_back(v);//adaug si nodul initial
else//daca nu s-a adaugat nimic
ns--;
}
if(minn<minlvl)
minlvl = minn;
}
return minlvl;//returneaza nivelul minim de intoarcere
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
fin>>x>>y;
V[x].push_back(y);
V[y].push_back(x);
}
for(int i=1;i<=n;++i)
if(!NIV[i])
DF(i,1);
fout<<ns<<endl;
for(int i=1;i<=ns;++i)
{
for(int j=0;j<S[i].size();++j)
fout<<S[i][j]<<" ";
fout<<endl;
}
fin.close();
fout.close();
return 0;
}