Pagini recente » Cod sursa (job #1862795) | Cod sursa (job #1676027) | Cod sursa (job #1209379) | Cod sursa (job #1847368) | Cod sursa (job #1638037)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 100003,M=200003;
int lst1[N],lst2[N],vf1[N],vf2[N],urm1[M],urm2[M],c[N],viz2[N],sol,lst3[N],urm3[M],vf3[N];
int nr2,nr3,nr1;
bool viz[N];
void adauga(int x,int y)
{
nr1++;
vf1[nr1]=y;
urm1[nr1]=lst1[x];
lst1[x]=nr1;
}
void adauga2(int x,int y)
{
nr2++;
vf2[nr2]=y;
urm2[nr2]=lst2[x];
lst2[x]=nr2;
}
void adauga3(int x,int y)
{
nr3++;
vf3[nr3]=y;
urm3[nr3]=lst3[x];
lst3[x]=nr3;
}
void dfs1(int x)
{
int y,p;
p=lst1[x];
viz[x]=true;
while(p!=0)
{
y=vf1[p];
if(!viz[y])
dfs1(y);
p=urm1[p];
}
c[++sol]=x;
}
void dfs2(int x)
{
int p, y;
viz2[x] = true;
p = lst2[x];
//out << x << " ";
adauga3(sol, x);
while(p != 0)
{
y = vf2[p];
if(!viz2[y]) dfs2(y);
p = urm2[p];
}
//c[++nr2] = x;
}
int main()
{
int n,m,i,x,y,p;
in>>n>>m;
for(i=1; i<=m; i++)
{
in>>x>>y;
adauga(x,y);
adauga2(y,x);
}
for(i = 1; i <= n; i++)
if(!viz[i])
dfs1(i);
sol = 0;
for(i = n; i >= 1; i--)
if(!viz2[c[i]])
{
sol++;
dfs2(c[i]);
//out << "\n";
}
out<<sol<<'\n';
for(i=1; i<=sol; i++)
{
p=lst3[i];
while(p!=0)
{
y = vf3[p];
out << y << " ";
p = urm3[p];
}
out<<'\n';
}
return 0;
}