Pagini recente » Cod sursa (job #1974919) | Cod sursa (job #2941305) | Cod sursa (job #583430) | Cod sursa (job #1778681) | Cod sursa (job #1759877)
using namespace std;
#include <fstream>
#include <vector>
FILE *f=fopen ("ctc.in","r");
FILE *g=fopen ("ctc.out", "w");
vector <int> G[100001],Gt[100001],C[100001];
int ord[100001],viz[100001],nr;
int nrc;
void dfs(int x)
{
viz[x]=1;
vector <int>::iterator it;
for(it=G[x].begin(); it!=G[x].end(); it++)
{
if(!viz[*it])
dfs(*it);
}
ord[++nr]=x;
}
void dfst (int x)
{
viz[x]=0;
C[nrc].push_back(x);
vector <int>::iterator it;
for(it=Gt[x].begin(); it!=Gt[x].end(); it++)
if(viz[*it])
dfst(*it);
}
int main()
{
int n,m,x,y,i;
fscanf(f,"%d%d",&n,&m);
while(m--)
{
fscanf (f,"%d%d",&x,&y);
G[x].push_back(y);
Gt[y].push_back(x);
}
for(i=1; i<=n; i++)
{
if(!viz[i])
dfs(i);
}
for(i=n; i>=1; i--)
{
if(viz[ord[i]])
{
nrc++;
dfst(ord[i]);
}
}
fprintf(g,"%d\n",nrc );
vector <int>::iterator it;
for(i=1; i<=nrc; i++)
{
for(it=C[i].begin(); it!=C[i].end(); it++)
{
fprintf(g,"%d ",*it);
}
fprintf(g,"\n");
}
return 0;
}