Pagini recente » Profil MarincasValentin | Cod sursa (job #2154943) | Cod sursa (job #2343503) | Cod sursa (job #1293382) | Cod sursa (job #406795)
Cod sursa(job #406795)
#include <cstdio>s
#define size 100010
using namespace std;
struct nod
{
int inf;
nod *next;
}*a[size],*rez[size],*at[size];
int n,m;
int nr_rez;
int viz[size];
int sir[size];
int nr;
void add(nod *&A,int a)
{
nod *q=new nod;
q->inf=a;
q->next=A;
A=q;
}
void citire()
{
int n1,n2;
scanf ("%d %d",&n,&m);
for (int i=0;i<m;i++)
{
scanf("%d %d",&n1,&n2);
add(a[n1],n2);
add(at[n2],n1);
}
}
void df(int n)
{
viz[n]=1;
for (nod *q=a[n];q;q=q->next)
if (!viz[q->inf])
df(q->inf);
sir[nr++]=n;
}
void df2(int n)
{
viz[n]=0;
add(rez[nr_rez],n);
for (nod *q=at[n];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);
for (int i=n-1;i>=0;i--)
if (viz[sir[i]])
{
df2(sir[i]);
nr_rez++;
}
}
void afish()
{
printf("%d\n",nr_rez);
for (int i=0;i<nr_rez;i++)
{
for (nod *j=rez[i];j;j=j->next)
printf("%d ",j->inf);
printf("\n");
}
}
int main ()
{
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
citire();
solve();
afish();
return 0;
}