Pagini recente » Cod sursa (job #486093) | Cod sursa (job #2375992) | Cod sursa (job #2115645) | Cod sursa (job #2905947) | Cod sursa (job #2298451)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
struct nod
{
int y;
nod* next;
}*a[100005],*trans[100005],*rez[100005];
bool viz1[100005],viz2[100005];
int steve[100005],k,nr;
void dfs1(int idnod)
{
viz1[idnod]=true;
nod* i=a[idnod];
while(i!=NULL)
{
if (viz1[i->y]==false)
dfs1(i->y);
i=i->next;
}
steve[k++]=idnod;
}
void dfs2(int idnod)
{
///afisare
nod* nou=new nod;
nou->y=idnod;
nou->next=rez[nr];
rez[nr]=nou;
//
viz2[idnod]=true;
//k--;
nod* i=trans[idnod];
while(i!=NULL)
{
if (viz2[i->y]==false)
dfs2(i->y);
i=i->next;
}
}
int main()
{
int n,m;
fin>>n>>m;
for (int i=0; i<m; i++)
{
int x,y;
fin>>x>>y;
nod* nou=new nod;
nou->y=y;
nou->next=a[x];
a[x]=nou;
nou=new nod;
nou->y=x;
nou->next=trans[y];
trans[y]=nou;
}
for (int i=1; i<=n; i++)
if (viz1[i]==false)
dfs1(i);
/*for (int i=0;i<k;i++)
cout<<steve[i]<<' ';
cout<<endl;*/
for (int i=k-1;i>=0;i--)
if (viz2[steve[i]]==false)
{
dfs2(steve[i]);
nr++;
}
fout<<nr<<'\n';
for (int i=0;i<nr;i++)
{
nod* j=rez[i];
while(j!=NULL)
{
fout<<j->y<<' ';
j=j->next;
}
fout<<'\n';
}
return 0;
}