Pagini recente » Cod sursa (job #493321) | Cod sursa (job #1851298) | Cod sursa (job #2022872) | Cod sursa (job #1382953) | Cod sursa (job #1568861)
#include <fstream>
#define N 100010
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,viz[N],timp[N],nrcomp;
struct nod
{
int info;
nod *urm;
};
nod *G[N], *Gt[N];
void Add(nod*&prim, int x)
{
nod *q=new nod;
q->info=x;
q->urm=prim;
prim=q;
}
void Citire()
{
int x,y;
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
Add(G[x],y);
Add(Gt[y],x);
}
}
void DFS(int x)
{
viz[x]=1;
for(nod *p=G[x];p!=NULL;p=p->urm)
if(viz[p->info]==0) DFS(p->info);
timp[++timp[0]]=x;
}
void DFST(int x)
{
viz[x]=0;
for(nod *p=Gt[x];p!=NULL;p=p->urm)
if(viz[p->info]==1) DFST(p->info);
}
void DFS_T(int x)
{
viz[x]=0;
fout<<x<<" ";
for(nod *p=Gt[x];p!=NULL;p=p->urm)
if(viz[p->info]==1) DFS_T(p->info);
}
int main()
{
Citire();
for(int i=1;i<=n;i++)
if(viz[i]==0) DFS(i);
for(int i=n;i>=1;i--)
if(viz[timp[i]]==1) {
nrcomp++;
DFST(timp[i]);
}
fout<<nrcomp<<"\n";
for(int i=1;i<=n;i++) viz[i]=1;
for(int i=n;i>=1;i--)
if(viz[timp[i]]==1) {
DFS_T(timp[i]);
fout<<"\n";
}
return 0;
}