Pagini recente » Cod sursa (job #305166) | Cod sursa (job #1820029) | Cod sursa (job #1074262) | Cod sursa (job #1483477) | Cod sursa (job #1652295)
#include <fstream>
#include <algorithm>
#include <stdlib.h>
#define NM 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct st{int x, y;};
st Stiva[NM];
int dfn[NM], low[NM], V[NM];
int * A[NM], * Sol[NM];
int n, m, nr, tot;
void Initializare()
{
int i;
for (i=1; i<=n; i++)
dfn[i]=-1;
}
void Afisare(int n, int x)
{
st p;
int last, i=0;
last=0;
do
{
p=Stiva[nr--];
V[++last]=p.x;
V[++last]=p.y;
}while (p.x!=n || p.y!=x);
sort (V+1, V+last+1);
tot++;
Sol[tot]= (int *) realloc(Sol[tot], sizeof(int));
Sol[tot][0]=0;
for (i=1; i<=last; i++)
{
if (V[i]!=V[i-1])
{
Sol[tot][0]++;
Sol[tot]= (int *) realloc(Sol[tot], (Sol[tot][0]+1)*sizeof(int));
Sol[tot][Sol[tot][0]]=V[i];
}
}
}
void DFS(int n, int mos, int lv)
{
int i, x;
dfn[n] = low[n] = lv;
for (i=1; i<=A[n][0]; i++)
{
x=A[n][i];
if (x==mos) continue;
if (dfn[x]==-1)
{
Stiva[++nr].x=n;
Stiva[nr].y=x;
DFS(x, n, lv+1);
low[n]=min(low[n], low[x]);
if (low[x]>=dfn[n])
{
Afisare(n, x);
}
}
else
low[n]=min(low[n], dfn[x]);
}
}
int main()
{
int i, x, y, j;
fin>>n>>m;
Initializare();
for (i=1; i<=n; i++)
{
A[i] = (int *) realloc (A[i], sizeof(int));
A[i][0]=0;
}
for (i=1; i<=m; i++)
{
fin>>x>>y;
A[x][0]++;
A[x] = (int *) realloc (A[x], (A[x][0]+1)*sizeof(int));
A[x][A[x][0]]=y;
A[y][0]++;
A[y] = (int *) realloc (A[y], (A[y][0]+1)*sizeof(int));
A[y][A[y][0]]=x;
}
DFS(1, 0, 0);
fout<<tot<<'\n';
for (i=1; i<=tot; i++)
{
for (j=1; j<=Sol[i][0]; j++)
{
fout<<Sol[i][j]<<" ";
}
fout<<'\n';
}
return 0;
}