Pagini recente » Cod sursa (job #147950) | Cod sursa (job #2362663) | Cod sursa (job #1645064) | Istoria paginii runda/preojii/clasament | Cod sursa (job #1318123)
#include<fstream>
#include<vector>
#define NMax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> G[NMax],GT[NMax],Sol[NMax];
int N,M,NrCTC,Use[NMax];
void Read()
{
f>>N>>M;
for(int i=1;i<=M;i++)
{
int x,y;
f>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
}
void DFSP(int Nod)
{
Use[Nod] = 1;
for(unsigned int i=0; i<G[Nod].size();i++)
{
int Vecin = G[Nod][i];
if(!Use[Vecin])
DFSP(Vecin);
}
}
void DFSM(int Nod,int k)
{
Use[Nod] = 2;
Sol[k].push_back(Nod);
for(unsigned int i=0; i<GT[Nod].size();i++)
{
int Vecin = GT[Nod][i];
if(Use[Vecin]==1)
DFSM(Vecin,k);
}
}
void Reset()
{
for(int i=1;i<=N;i++)
if(Use[i]==1)
Use[i]=0;
}
void Solve()
{
int k=0;
for(int i=1;i<=N;i++)
{
if(!Use[i])
{
k++;
DFSP(i);
NrCTC++;
DFSM(i,k);
Reset();
}
}
g<<NrCTC<<'\n';
for(int i=1;i<=NrCTC;i++)
{
for(int j=0;j<Sol[i].size();j++)
g<<Sol[i][j]<<" ";
g<<'\n';
}
}
int main()
{
Read();
Solve();
return 0;
}