Pagini recente » Cod sursa (job #2700686) | Cod sursa (job #732658) | Cod sursa (job #2794719) | Cod sursa (job #1225018) | Cod sursa (job #2715523)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int p,afis,n,m,nush[100005],nivel[100005],nma[100005],stiva[100005],niv=0,rad,nr,nr11;
int nr1;
int afis2[100005],nr2;
int afis3[100005][3],nr3;
vector < int > afis1[100005];
struct nod
{
int info;
nod *urm;
};
nod *v[100005];
void adaug(int i,int j)
{
nod *q;
q=new nod;
q->info=j;
q->urm=v[i];
v[i]=q;
}
void citire()
{
int i,j;
fin>>n>>m;
while (m!=0)
{
fin>>i>>j;
adaug(i,j);
adaug(j,i);
m--;
}
}
void DFS(int k,int tata)
{
int x,nr=0;
nod *q;
nush[k]=1;
stiva[++niv]=k;
nivel[k]=nivel[tata]+1;
nma[k]=nivel[k];
q=v[k];
while (q!=NULL)
{
x=q->info;
if (x!=tata)
{
if (nush[x]==1)
{
if (nma[k]>nivel[x])
nma[k]=nivel[x];
}
else
{
nr++;
DFS(x,k);
if (nma[k]>nma[x])
nma[k]=nma[x];
if (p==1)
{
if (nivel[k]<=nma[x])
{
nr1++;
while(stiva[niv]!=x)
{
afis1[nr1].push_back(stiva[niv]);
niv--;
}
afis1[nr1].push_back(x);
niv--;
afis1[nr1].push_back(k);
///niv--;
}
}
if (p==2)
{
if (nivel[k]<=nma[x] and k!=rad)
{
afis2[k]=1;
}
}
if (p==3)
{
if (nivel[k]<nma[x])
{
///fout<<k<<" "<<x<<'\n';
nr3++;
afis3[nr3][1]=k;
afis3[nr3][2]=x;
}
}
}
}
q=q->urm;
}
if (k==rad and nr>1)
{
afis2[k]=1;
}
}
int main()
{
int i,j;
///fin>>p;
citire();
p=1;
for (i=1;i<=n;i++)
{
if (nush[i]==0)
{
rad=i;
DFS(i,0);
}
}
if (p==1)
{
fout<<nr1<<'\n';
for (i=1;i<=nr1;i++)
{
nr11=afis1[i].size();
///fout<<nr11<<" ";
for (j=0;j<nr11;j++)
fout<<afis1[i][j]<<" ";
fout<<'\n';
}
}
if (p==2)
{
nr2=0;
for (i=1;i<=n;i++)
if (afis2[i]==1)
nr2++;
fout<<nr2<<'\n';
for (i=1;i<=n;i++)
if (afis2[i]==1)
fout<<i<<" ";
}
if (p==3)
{
fout<<nr3<<'\n';
for (i=1;i<=nr3;i++)
fout<<afis3[i][1]<<" "<<afis3[i][2]<<'\n';
}
/// fout<<afis<<'\n';
/*for (i=1; i<=n; i++)
fout<<i<<" ";
fout<<'\n';
for (i=1; i<=n; i++)
fout<<nivel[i]<<" ";
fout<<'\n';
for (i=1; i<=n; i++)
fout<<nma[i]<<" ";*/
return 0;
}