Pagini recente » Cod sursa (job #497858) | Cod sursa (job #1218362) | Cod sursa (job #1239658) | Cod sursa (job #545378) | Cod sursa (job #1878868)
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("ctc.in");
ofstream out ("ctc.out");
const int NMax=100005;
int n, m, use[NMax], nrctc, nr, x[NMax];
vector <int> G[NMax], sol[NMax], GT[NMax];
void Read()
{
in>>n>>m;
while(m--)
{
int x,y;
in>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void dfs_secund(int nodarg)
{
sol[nrctc].push_back(nodarg);
use[nodarg]=0;
for (int i=0;i<(int)GT[nodarg].size();i++)
{
int vecin=GT[nodarg][i];
if(use[vecin]==1)
{
dfs_secund(vecin);
}
}
}
void dfs_prim(int nodarg)
{
use[nodarg]=1;
for(int i=0;i<(int)G[nodarg].size();i++)
{
int vecin=G[nodarg][i];
if(use[vecin]==0)
{
dfs_prim(vecin);
}
}
x[++nr]=nodarg;
}
void Solve()
{
for (int i=1;i<=n;i++)
{
if(!use[i])
dfs_prim(i);
}
for (int i=n;i>=1;i--)
{
if(use[x[i]]==1)
{
nrctc++;
dfs_secund(x[i]);
}
}
}
void Print()
{
out<<nrctc<<'\n';
for(int i=1;i<=nrctc;i++)
{
for(int j=0;j<(int)sol[i].size();j++)
{
out<<sol[i][j]<<' ';
}
out<<'\n';
}
}
int main()
{
Read();
Solve();
Print();
}