Pagini recente » Cod sursa (job #2563510) | Cod sursa (job #231270) | Cod sursa (job #2533149) | Cod sursa (job #2661627) | Cod sursa (job #1916605)
#include <fstream>
#include <vector>
#include <Queue>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector<int> Gf[101],Gft[101],Dfs1;
queue<int>Q;
int n,m,nr;
int viz[101],comp[101];
void Citire()
{
int x=0,y=0;
cin>>n>>m;
for(int i=1;i<=m;++i)
{
cin>>x>>y;
Gf[x].push_back(y);
Gft[y].push_back(x);
}
}
void DFS(int nod)
{
viz[nod]=1;
for(int i=0;i<Gf[nod].size();++i)
{
if(viz[Gf[nod][i]]==0)
DFS(Gf[nod][i]);
}
Dfs1.push_back(nod);
}
void DFT(int nod,int c)
{
viz[nod]=0;
comp[nod]=c;
Q.push(nod);
for(int i=0;i<Gft[nod].size();++i)
{
if(viz[Gft[nod][i]]==1)
DFT(Gft[nod][i],c);
}
}
int main()
{
Citire();
for(int j=1;j<=n;++j)
if(viz[j]==0)
DFS(j);
for(int j=Dfs1.size()-1;j>=0;--j)
if(viz[Dfs1[j]])
{
DFT(Dfs1[j],++nr);
Q.push(-1);
}
cout<<nr<<'\n';
while(!Q.empty())
{
if(Q.front()==-1)
cout<<'\n';
else
cout<<Q.front()<<' ';
Q.pop();
}
return 0;
}