Pagini recente » Cod sursa (job #1660067) | Cod sursa (job #833514) | Cod sursa (job #3194079) | Cod sursa (job #1577984) | Cod sursa (job #866418)
Cod sursa(job #866418)
#include<cstdio>
#define M 100002
#define min(a,b) ((a)>(b)?(b):(a))
using namespace std;
struct Graf
{
int v;
Graf *urm;
};
Graf *a[M], *sol[M];
int nr,n,m,viz[M],niv[M],jos[M],st[M], cap,nivel;
inline void insert(int x, int y, Graf *a[])
{
Graf *p;
p=new Graf;
p->v = y;
p->urm = a[x];
a[x] = p;
}
void citire()
{
freopen("ctc.in","r","stdin");
int x,y;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&x,&y);
insert(x,y,a);
}
}
void ctc(int nod)
{
st[++cap]=nod;
Graf *q;
niv[nod] = jos[nod] = ++nivel;
for(q=a[nod];q;q=q->urm)
{
if(!niv[q->v])
{
ctc(q->v);
jos[nod]=min(jos[nod], jos[q->v]);
}
else if(niv[q->v] > 0) jos[nod]=min(jos[nod], niv[q->v]);
}
if(niv[nod] == jos[nod])
{
++nr;
do
{
insert(nr, st[cap], sol);
niv[st[cap]]=-1;
cap--;
}
while(st[cap+1]!=nod);
}
}
void afisare()
{
freopen("ctc.out","w","stdout");
printf("%d\n",nr);
int i;
Graf *q;
for(i=1;i<=nr;++i)
{
for(q=sol[i];q;q=q->urm)
printf("%d ",q->v);
printf("\n");
}
}
int main()
{
int i;
citire();
for(i=1;i<=n;++i)
if(!niv[i])
ctc(i);
afisare();
return 0;
}