Pagini recente » Cod sursa (job #1971285) | Cod sursa (job #665587) | Cod sursa (job #1678079) | Cod sursa (job #1642495) | Cod sursa (job #671246)
Cod sursa(job #671246)
#include <iostream>
#include <fstream>
#define maxN 100005
#define maxM 200005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,ST[maxN],nr=0,saw[maxN],nr_cc=0;
struct list
{
int nod;
list *next;
} *G[maxN],*GT[maxN];
struct list_cc
{
int nod;
list_cc *next;
} *Lcc[maxN];
void addN(int x,int y)
{
list *p,*q;
q=new list;
q->nod=y;
q->next=G[x];
G[x]=q;
p=new list;
p->nod=x;
p->next=GT[y];
GT[y]=p;
}
void reset_saw()
{
for(int i=1; i<=n ;i++)
saw[i]=0;
}
void read_ini()
{
f>>n; f>>m;
int i,a,b;
for(i=1; i<=m ;i++)
{
f>>a; f>>b;
addN(a,b);
}
reset_saw();
}
void DFg(int s)
{
list *p;
saw[s]=1;
for(p=G[s]; p!=NULL ;p=p->next)
{
if(!saw[p->nod])
DFg(p->nod);
}
ST[nr++]=s;
}
void DFgt(int s)
{
list *q;
list_cc *p;
p=new list_cc;
p->nod=s;
p->next=Lcc[nr_cc];
Lcc[nr_cc]=p;
saw[s]=1;
for(q=GT[s]; q!=NULL ;q=q->next)
{
if(!saw[q->nod])
DFgt(q->nod);
}
}
void print_cc()
{
int i;
list_cc *q;
g<<nr_cc<<"\n";
for(i=1; i<=nr_cc ;i++)
{
q=Lcc[i];
while(q)
{
g<<q->nod<<" ";
q=q->next;
}
g<<"\n";
}
}
int main()
{
read_ini();
int i;
for(i=1; i<=n ;i++)
{
if(!saw[i])
DFg(i);
}
reset_saw();
for(i=n-1; i>=0 ;i--)
{
if(!saw[ST[i]])
{
nr_cc++;
DFgt(ST[i]);
}
}
print_cc();
return 0;
}