Pagini recente » Cod sursa (job #1319258) | Cod sursa (job #2865803) | Cod sursa (job #376970) | Cod sursa (job #1480935) | Cod sursa (job #2538421)
#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 comp(int nod,int fiu)
{
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 dfs(int nod,int nivel)
{
viz[nod]=1;
int fiu;
niv[nod]=low[nod]=nivel;
s[++nn]=nod;
for(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,nivel+1);
low[nod]=min(low[nod],low[fiu]);
if(niv[nod]<=low[fiu])
sol++,comp(nod,fiu);
}
}
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(1,0);
afisare();
x.close();
y.close();
return 0;
}