Pagini recente » Cod sursa (job #1378656) | Cod sursa (job #3039288) | Cod sursa (job #3120966) | Cod sursa (job #1264673) | Cod sursa (job #398337)
Cod sursa(job #398337)
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX=100004;
const int MMAX=200004;
vector <int> A[NMAX],CB[NMAX];
int dfn[NMAX],low[NMAX], S[MMAX][2],nv[NMAX];
int ns,n,ncb;
bool viz[NMAX];
void citire()
{
FILE *fin=fopen("biconex.in","r");
int m;
fscanf(fin,"%d%d",&n,&m);
int x,y;
while (m--)
{
fscanf(fin,"%d%d",&x,&y);
A[x].push_back(y);
A[y].push_back(x);
}
for (int i=1;i<=n;++i) nv[i]=A[i].size();
fclose(fin);
}
void comp_bicon(int tx, int x)
{
ncb++;
do
{
CB[ncb].push_back(S[ns][1]);
}
while (S[ns--][0]!=tx);
CB[ncb].push_back(S[ns+1][0]);
}
void biconex(int tx, int x)
{ int i,y;
dfn[x]=low[x]=dfn[tx]+1; viz[x]=1;
for (i=0;i<nv[x];++i)
{
y=A[x][i];
if (y==tx) continue;
if (viz[y]) { low[x]=min(low[x],dfn[y]);}
else
{
S[++ns][0]=x; S[ns][1]=y;
biconex(x,y);
low[x]=min(low[x],low[y]);
if (low[y]>=dfn[x]) comp_bicon(x,y);
}
}
}
void afisare()
{
FILE *fout=fopen("biconex.out","w");
fprintf(fout,"%d\n",ncb);
int i,j;
for (i=1;i<=ncb;++i)
{
for (j=CB[i].size()-1; j>=0;--j)
fprintf(fout,"%d ",CB[i][j]);
fprintf(fout,"\n");
}
fclose(fout);
}
int main()
{
citire();
ns=ncb=0;
for (int i=1;i<=n;++i)
if (!viz[i]) biconex(0,i);
afisare();
return 0;
}