Pagini recente » Cod sursa (job #2572027) | Cod sursa (job #2795990) | Cod sursa (job #1575059) | Cod sursa (job #2932731) | Cod sursa (job #283532)
Cod sursa(job #283532)
#include <stdio.h>
const long NMAX=100010;
const long MMAX=200010;
long *a[NMAX], *b[NMAX], da[MMAX], db[MMAX], x[MMAX], y[MMAX], q[NMAX], p, u, n, m, comp[NMAX], cont;
bool viz[NMAX];
void bfa(long nod);
void bfb(long nod);
int main()
{
long i, j, k;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%ld%ld", &n, &m);
for (i=0; i<m; i++)
{
scanf("%ld%ld", &x[i], &y[i]);
da[x[i]]++;
db[y[i]]++;
}//for i
for (i=1; i<=n; i++)
{
a[i]=new long(da[i]+1);
a[i][0]=0;
b[i]=new long(db[i]+1);
b[i][0]=0;
}//for i
for (i=0; i<m; i++)
{
a[x[i]][++a[x[i]][0]]=y[i];
b[y[i]][++b[y[i]][0]]=x[i];
}//for i
cont=0;
k=1;
while (k<=n)
{
cont++;
bfa(k);
for (i=0; i<=u; i++)
if (comp[q[i]]<=0)
comp[q[i]]=-cont;
bfb(k);
for (i=0; i<=u; i++)
if (comp[q[i]]==-cont)
comp[q[i]]=cont;
while ((comp[k]>0)&&(k<=n))
k++;
}//while
printf("%ld\n", cont);
for (i=1; i<=cont; i++)
{
for (j=1; j<=n; j++)
if (comp[j]==i)
printf("%ld ", j);
printf("\n");
}//for i
return 0;
}//main
void bfa(long nod)
{
long i;
for (i=1; i<=n; i++)
viz[i]=0;
p=0;
u=0;
q[u]=nod;
viz[nod]=1;
while (p<=u)
{
nod=q[p++];
for (i=1; i<=a[nod][0]; i++)
if (!viz[a[nod][i]])
{
viz[a[nod][i]]=1;
q[++u]=a[nod][i];
}//if
}//while
}//bfa
void bfb(long nod)
{
long i;
for (i=1; i<=n; i++)
viz[i]=0;
p=0;
u=0;
q[u]=nod;
viz[nod]=1;
while (p<=u)
{
nod=q[p++];
for (i=1; i<=b[nod][0]; i++)
if (!viz[b[nod][i]])
{
viz[b[nod][i]]=1;
q[++u]=b[nod][i];
}//if
}//while
}//bfb