Pagini recente » Cod sursa (job #638026) | Cod sursa (job #2709873) | Cod sursa (job #1117381) | Cod sursa (job #2400226) | Cod sursa (job #2314510)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> Ad[100001];
vector <int> Ad_rev[100001];
int viz[100001];
int N,M;
vector <int> S;
void SortTop(int x)
{
viz[x]=1;
for(int i=0;i<Ad[x].size();++i)
if(!viz[Ad[x][i]])SortTop(Ad[x][i]);
S.push_back(x);
}
void Read()
{
int x,y;
fin>>N>>M;
for(int i=1;i<=M;++i)
{
fin>>x>>y;
Ad[x].push_back(y);
Ad_rev[y].push_back(x);
}
SortTop(1);
}
void DFS(int x,bool c)
{
viz[x]=1;
if(c==1)fout<<x<<" ";
for(int i=0;i<Ad_rev[x].size();++i)
if(viz[Ad_rev[x][i]]==0)DFS(Ad_rev[x][i],c);
}
void Solve()
{
for(int i=1;i<=N;++i)viz[i]=0;
int nr_comp=0;
for(int i=S.size()-1;i>=0;--i)
{
if(viz[S[i]]==0){DFS(S[i],0);nr_comp++;}
}
fout<<nr_comp<<"\n";
for(int i=1;i<=N;++i)viz[i]=0;
for(int i=S.size()-1;i>=0;--i)
{
if(viz[S[i]]==0){DFS(S[i],1);fout<<"\n";}
}
}
int main()
{
Read();
Solve();
return 0;
}