Pagini recente » Cod sursa (job #1349026) | Cod sursa (job #3209055) | Cod sursa (job #3169817) | Cod sursa (job #3277330) | Cod sursa (job #251866)
Cod sursa(job #251866)
#include<stdio.h>
#define M 100002
#define min(a,b) ((a)>(b)?(b):(a))
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
struct Graf
{
int v;
Graf *urm;
};
Graf *G[M];
Graf *sol[M];
int nr;
int n,m;
int viz[M];
int niv[M];
int low[M];
int st[M], vf;
int nivel;
inline void insert(int x, int y, Graf *G[])
{
Graf *p;
p=new Graf;
p->v = y;
p->urm = G[x];
G[x] = p;
}
void read()
{
int x,y;
fscanf(f,"%d%d",&n,&m);
while(m--)
{
fscanf(f,"%d%d",&x,&y);
insert(x,y, G);
}
}
void tare_conexe(int nod)
{
st[++vf]=nod;
Graf *q;
niv[nod] = low[nod] = ++nivel;
for(q=G[nod];q;q=q->urm)
{
if(!niv[q->v])
{
tare_conexe(q->v);
low[nod]=min(low[nod], low[q->v]);
}
else if(niv[q->v] > 0) low[nod]=min(low[nod], niv[q->v]);
}
if(niv[nod] == low[nod])
{
// elimin din stiva pana cand st[vf] != nod
++nr;
do
{
insert(nr, st[vf], sol);
niv[st[vf]]=-1;
vf--;
}
while(st[vf+1]!=nod);
}
}
void print()
{
fprintf(g,"%d\n",nr);
int i;
Graf *q;
for(i=1;i<=nr;++i)
{
for(q=sol[i];q;q=q->urm)
fprintf(g,"%d ",q->v);
fprintf(g,"\n");
}
}
int main()
{
int i;
read();
for(i=1;i<=n;++i)
if(!niv[i]) tare_conexe(i);
print();
return 0;
}