Pagini recente » Cod sursa (job #1570488) | Cod sursa (job #2923949) | Cod sursa (job #1654598) | Cod sursa (job #24719) | Cod sursa (job #1565502)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100005
using namespace std;
vector<int> vec[nmax],invec[nmax],L,Sol[nmax];//out-neighbour; in-noughbour
int n,m,viz[nmax],k,comp[nmax],NrComp;
void citire()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
{
scanf("%d%d",&x,&y);
vec[x].push_back(y);
invec[y].push_back(x);
}
}
void vizitare(int u)
{
if(viz[u])
return;
viz[u]=1;
for(int i=0;i<vec[u].size();++i)
vizitare(vec[u][i]);
L.push_back(u);
}
void creazaComponenta(int u,int componenta)
{
comp[u]=componenta;
Sol[componenta].push_back(u);
for(int i=0; i<invec[u].size(); ++i)
{
int nod=invec[u][i];
if(!comp[nod])
creazaComponenta(nod,componenta);
}
}
int main()
{
freopen("ctc.in","rt",stdin);
freopen("ctc.out","wt",stdout);
citire();
for(int u=1; u<=n; u++)
vizitare(u);
while(L.size())
{
if(comp[L.back()]==0)
creazaComponenta(L.back(),++NrComp);
L.pop_back();
}
cout<<NrComp<<'\n';
for(int i=1; i<=NrComp; i++)
{
for(int j=0; j<Sol[i].size(); j++)
cout<<Sol[i][j]<<' ';
cout<<'\n';
}
}