Pagini recente » Cod sursa (job #2372802) | Cod sursa (job #2098599) | Cod sursa (job #2294820) | Cod sursa (job #982225) | Cod sursa (job #280041)
Cod sursa(job #280041)
//Componente tare conxe BC
#include <stdio.h>
#include <fstream.h>
#define lg_max 100010
struct no
{
int inf;
no *next;
}*G[lg_max],*GT[lg_max],*rez[lg_max],*aux;
int sir[lg_max],num,n,m;
char viz[lg_max];
void baga(no *&X,int dest)
{
no *q=new no;
q->inf=dest;
q->next=X;
X=q;
}
void citire()
{
int x,y;
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
scanf ("%d %d",&n,&m);
for (int i=0;i<m;i++)
{
scanf ("%d %d",&x,&y);
baga(G[x],y);
baga(GT[y],x);
}
}
void df(int nod)
{
viz[nod]='1';
for (no *q=G[nod];q;q=q->next)
if (!viz[q->inf])
df(q->inf);
sir[num++]=nod;
}
void df2(int nod)
{
viz[nod]='1';
aux=new no;
aux->inf=nod;
aux->next=rez[num];
rez[num]=aux;
for (no *q=GT[nod];q;q=q->next)
if (!viz[q->inf])
df2(q->inf);
}
void solve()
{
for (int i=1;i<=n;i++)
if (!viz[i])
df(i);
memset(viz,0,sizeof(viz));
num=0;
for (int j=n-1;j>=0;j--)
if(!viz[sir[j]])
{
df2(sir[j]);
num++;
}
//afisare();
printf("%d\n",num);
for (int p=0;p<num;p++)
{
for (no *q=rez[p];q;q=q->next)
printf("%d ",q->inf);
printf("\n");
}
}
int main ()
{
citire();
solve();
return 0;
}