Pagini recente » Cod sursa (job #2305319) | Cod sursa (job #2689788) | Cod sursa (job #2433172) | Cod sursa (job #1875300) | Cod sursa (job #2195431)
#include <stdio.h>
#include <vector>
#include <bitset>
using namespace std;
FILE *f,*g;
int st[100000];
bitset <100002> fr;
vector <int> ctc[100002];
int a[2][400002],v[100002],aGT[2][400002],vGT[100002];
int m,n,sol;
void read()
{ int i,j,k=0,kk=0;
fscanf(f,"%d %d",&n,&m);
for(int l=1; l<=m; l++)
{
fscanf(f,"%d %d",&i,&j);
++k;
a[0][k]=j;
a[1][k]=v[i];
v[i]=k;
++kk;
aGT[0][kk]=i;
aGT[1][kk]=vGT[j];
vGT[j]=kk;
}
}
void dfs(int nod)
{ int ok;
fr[nod]=1;
ok=v[nod];
while(ok)
{
if(!fr[a[0][ok]])
dfs(a[0][ok]);
ok=a[1][ok];
}
st[++st[0]]=nod;
}
void dfst(int nod)
{ int ok;
fr[nod]=1;
ok=vGT[nod];
while(ok)
{
if(!fr[aGT[0][ok]])
dfst(aGT[0][ok]);
ok=aGT[1][ok];
}
ctc[sol].push_back(nod);
}
int main()
{ int i,j;
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
read();
for(i=1;i<=n;i++)
{
if(!fr[i])
dfs(i);
}
for(i=1;i<=n;i++)
fr[i]=0;
for(i=n;i>=1;i--)
{
if(!fr[st[i]])
{
sol++;
dfst(st[i]);
}
}
fprintf(g,"%d\n",sol);
for(i=1;i<=sol;i++)
{
for(j=0;j<ctc[i].size();j++)
fprintf(g,"%d ",ctc[i][j]);
fprintf(g,"\n");
}
fclose(f);
fclose(g);
return 0;
}