Pagini recente » Cod sursa (job #1182074) | Cod sursa (job #2887490) | Cod sursa (job #1004353) | Cod sursa (job #944009) | Cod sursa (job #1106390)
#include<fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct nod
{
int inf;
nod* leg;
};
typedef nod* PNod;
PNod G[100001],Gt[100001],sol[100005];
int viz1[100001],stiv[100001],n,m,t,nrc;
void add1(int x,int y)
{
PNod p=new nod;
p->inf=y;
p->leg=G[x];
G[x]=p;
}
void add2(int x,int y)
{
PNod p=new nod;
p->inf=y;
p->leg=Gt[x];
Gt[x]=p;
}
void add3(int x,int y)
{
PNod p=new nod;
p->inf=y;
p->leg=sol[x];
sol[x]=p;
}
void df1(int i)
{
PNod p;
viz1[i]=1;
for( p=G[i];p;p=p->leg)
if(viz1[p->inf]==0)
df1(p->inf);
t++;
stiv[t]=i;
}
void df2(int i,int poz)
{
viz1[i]=1;
add3(poz,i);
for(PNod p=Gt[i];p;p=p->leg)
if(viz1[p->inf]==0)
{
df2(p->inf,poz);
}
}
void ccon()
{
int i;
for(i=n;i>=1;i--)
{
if(viz1[i]==0)
{df1(i);}
}
for(i=1;i<=n;i++)
viz1[i]=0;
for(i=n;i>=1;i--)
{
if(viz1[stiv[i]]==0)
{
nrc++;
df2(stiv[i],nrc);
}
}
g<<nrc<<'\n';
for(i=1;i<=nrc;i++)
{
for(PNod p=sol[i];p;p=p->leg)
g<<p->inf<<" ";
g<<'\n';
}
}
int main()
{
int i,x,y;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
add1(x,y);
add2(y,x);
}
ccon();
return 0;
}