Pagini recente » Cod sursa (job #2337138) | Cod sursa (job #2038929) | Cod sursa (job #745025) | Cod sursa (job #2889253) | Cod sursa (job #2048164)
#include <fstream>
#include <vector>
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");
ofstream fout("ctc.out");
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;
for (i=1;i<=m;i++)
{
fin>>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;
for (i = 1; i <= k; i++)
{
for (j=0; j < ctc[i].size(); j++)
fout<<ctc[i][j]<<' ';
fout<<endl;
}
return 0;
}