Pagini recente » Cod sursa (job #940002) | Cod sursa (job #2672796) | Cod sursa (job #1916205) | Cod sursa (job #1969021) | Cod sursa (job #2048180)
#include <fstream>
#include <vector>
#include<stdio.h>
using namespace std;
#define NM 100005
int n,m,t[NM], p, viz[NM], k;
vector<int> G[NM], GT[NM], ctc[NM];
//ifstream fin("ctc.in");
FILE *fin=fopen("ctc.in","r");
//ofstream fout("ctc.out");
FILE *fout=fopen("ctc.out","w");
void DFS(int x)
{
int i, w;
viz[x] = 1;
for (i = 0;i< G[x].size();i++)
{
w=G[x][i];
if (!viz[w])
DFS(w);
}
p++;t[p] = x;
}
void DFST(int x)
{
int i, w;
viz[x] = k;
ctc[k].push_back(x);
for (i = 0;i<GT[x].size(); i++)
{
w=GT[x][i];
if (!viz[w])
DFST(w);
}
}
int main()
{
int i,j, x, y;
///fin>>n>>m;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=m;i++)
{
//fin>>x>>y;
fscanf(fin,"%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=1;i<=n;i++)
viz[i]=0;
for (i = n; i>=1; i--)
if (!viz[t[i]])
{
k++;
DFST(t[i]);
}
///fout<<k<<endl;
fprintf(fout,"%d\n",k);
for (i = 1; i <= k; i++)
{
for (j=0; j < ctc[i].size(); j++)
fprintf(fout,"%d ",ctc[i][j]);
///fout<<ctc[i][j]<<' ';
///fout<<endl;
fprintf(fout,"\n");
}
return 0;
}