Pagini recente » Cod sursa (job #3204279) | Cod sursa (job #2430247) | Cod sursa (job #990139) | Cod sursa (job #16070) | Cod sursa (job #281166)
Cod sursa(job #281166)
#include <stdio.h>
#define dim 100100
struct nod
{
int nr;
nod *urm;
};
int n, m, plus[dim], minus[dim], ct, fol[dim];
nod *g[dim], *gt[dim];
void add(nod *&p, int nr)
{
nod *n1=new nod;
n1->nr=nr;
n1->urm=p;
p=n1;
}
void dfp(int x)
{
nod *n1;
plus[x]=1;
n1=g[x];
while (n1)
{
if (!plus[n1->nr]) dfp(n1->nr);
n1=n1->urm;
}
}
void dfm(int x)
{
nod *n1;
minus[x]=1;
n1=gt[x];
while (n1)
{
if (!minus[n1->nr]) dfm(n1->nr);
n1=n1->urm;
}
}
void conex()
{
int i, j;
ct=1;
for (i=1; i<=n; i++)
{
if (!fol[i])
{
dfp(i);
dfm(i);
for (j=i; j<=n; j++)
{
if (plus[j]*minus[j])
fol[j]=ct;
plus[j]=minus[j]=0;
}
ct++;
}
}
}
int main()
{
int a, b;
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d %d\n", &n, &m);
for (; m; m--)
{
scanf("%d %d\n", &a, &b);
add(g[a], b);
add(gt[b], a);
}
conex();
printf("%d\n", --ct);
for (; ct; ct--)
{
for (int i=1; i<=n; i++)
if (fol[i]==ct) printf("%d ", i);
printf("\n");
}
return 0;
}