Pagini recente » Cod sursa (job #1305683) | Cod sursa (job #2524068) | Cod sursa (job #783391) | Cod sursa (job #102911) | Cod sursa (job #2538545)
#include <iostream>
#include <fstream>
#include <stdlib.h>
#define N 100002
using namespace std;
ifstream x("biconex.in");
ofstream y("biconex.out");
int n,m,i,j,k;
int niv[N],low[N],t[N],nn,nivel,sol,viz[N];
int *a[N],*b[N],s[N];
void citire()
{
x>>n>>m;
for(i=1;i<=n;i++)
{
a[i]=(int *) realloc(a[i],sizeof(int));
a[i][0]=0;
}
for(k=1;k<=m;k++)
{
x>>i>>j;
a[i][0]++;
a[i]=(int *) realloc(a[i],(a[i][0]+1)*sizeof(int));
a[i][a[i][0]]=j;
a[j][0]++;
a[j]=(int *) realloc(a[j],(a[j][0]+1)*sizeof(int));
a[j][a[j][0]]=i;
}
}
void dfs(int nod)
{
int fiu;
viz[nod]=1;
niv[nod]=low[nod]=niv[t[nod]]+1;
s[++nn]=nod;
for(int j=1;j<=a[nod][0];j++)
{
fiu=a[nod][j];
if(viz[fiu])
{
if(fiu!=t[nod])
low[nod]=min(low[nod],niv[fiu]);
continue;
}
t[fiu]=nod;
dfs(fiu);
low[nod]=min(low[fiu],low[nod]);
if(niv[nod]<=low[fiu])
{
sol++;
b[sol]=(int *)realloc(b[sol],sizeof(int));
b[sol][0]=0;
do
{
k=s[nn];
b[sol][0]++;
b[sol]=(int *)realloc(b[sol],(b[sol][0]+1)*sizeof(int));
b[sol][b[sol][0]]=k;
nn--;
}while(k!=fiu);
b[sol][0]++;
b[sol]=(int *)realloc(b[sol],(b[sol][0]+1)*sizeof(int));
b[sol][b[sol][0]]=nod;
}
}
}
void afisare()
{
y<<sol<<'\n';
for(i=1;i<=sol;i++)
{
for(j=1;j<=b[i][0];j++)
y<<b[i][j]<<" ";
y<<'\n';
}
}
int main()
{
citire();
for(i=1;i<=n;i++)
if(!viz[i])
t[i]=0,dfs(i);
afisare();
x.close();
y.close();
return 0;
}