Pagini recente » Cod sursa (job #1638011) | Cod sursa (job #1904111) | Cod sursa (job #771310) | Cod sursa (job #2449406) | Cod sursa (job #2254674)
#include <bits/stdc++.h>
#define Dim 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int N,M,x,y,POST[Dim],cnt,ans;
bool viz[Dim],vizT[Dim];
vector < int > Vf[Dim],VT[Dim],CTC[Dim];
void Citire()
{
f>>N>>M;
for(int i=1;i<=M;i++)
{
f>>x>>y;
Vf[x].push_back(y);
VT[y].push_back(x);
}
}
void DFS(int nod)
{
for(unsigned int i=0;i<Vf[nod].size();i++)
if(!viz[Vf[nod][i]])
{
viz[Vf[nod][i]]=1;
DFS(Vf[nod][i]);
}
POST[++cnt]=nod;
}
void DFST(int nod)
{
CTC[ans].push_back(nod);
for(unsigned int i=0;i<VT[nod].size();i++)
if(!vizT[VT[nod][i]])
{
vizT[VT[nod][i]]=1;
DFST(VT[nod][i]);
}
}
int main()
{
Citire();
for(int i=1;i<=N;i++)
if(!viz[i])
{
viz[i]=1;
DFS(i);
}
for(int i=cnt;i>=1;i--)
if(!vizT[POST[i]])
{
ans++;
vizT[POST[i]]=1;
DFST(POST[i]);
}
g<<ans;
for(int i=1;i<=ans;i++)
{
g<<'\n';
for(unsigned int j=0;j<CTC[i].size();j++)
g<<CTC[i][j]<<" ";
}
return 0;
}