Pagini recente » Cod sursa (job #1394923) | Cod sursa (job #2770315) | Cod sursa (job #3261096) | Cod sursa (job #1905017) | Cod sursa (job #1357267)
#include <fstream>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N=100001, M=200001;
int n,nrm,nr,nrc;
int lst[N], lstt[N], vft[M], urmt[M], mt, vf[M], urm[M], m,c[N];
bool viz[N];
int vizt[N];
void dfs(int x)
{
int p = lst[x], y;
viz[x] = true;
while(p != 0)
{
y = vf[p];
if (!viz[y])
dfs(y);
p = urm[p];
}
c[++nr] = x;
}
void dfst(int x,int mark){
int p = lstt[x], y;
vizt[x] = mark;
while(p != 0)
{
y = vft[p];
if (!vizt[y])
dfst(y,mark);
p = urmt[p];
}
}
void adaug(int x, int y)
{
m++;
vf[m] = y;
urm[m] = lst[x];
lst[x] = m;
}
void adaugt(int x, int y)
{
mt++;
vft[m] = x;
urmt[m] = lstt[y];
lstt[y] = mt;
}
int main()
{
int i,j,x,y,cod,p,nod;
in>>n>>nrm;
for(i=1;i<=nrm;i++){
in>>x>>y;
cod=1;
p = lst[x];
while(p != 0)
{
nod = vf[p];
p = urm[p];
if(nod==y)
cod=0;
}
if(cod==1)
adaug(x,y);
cod=1;
p=lstt[y];
while(p!=0){
nod=vft[p];
p=urmt[p];
if(nod==x)
cod=0;
}
if(cod==1)
adaugt(x,y);
}
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
y=0;
for(i=nr;i>=1;i--){
x=c[i];
if(!vizt[x]){
y++;
dfst(x,y);
}
}
out<<y<<"\n";
for(i=1;i<=y;i++){
for(j=1;j<=n;j++)
if(vizt[j]==i)
out<<j<<" ";
out<<"\n";
}
return 0;
}