Pagini recente » Cod sursa (job #1112456) | Cod sursa (job #488016) | Cod sursa (job #2551271) | Cod sursa (job #207994) | Cod sursa (job #1904529)
#include <cstdio>
#include <vector>
const int Q=100007;
int n,m;
std::vector<int> grph[Q],invg[Q];
void read_data()
{
scanf("%d%d",&n,&m);
int a,b;
for(int i=1; i<=m; i++)
{
scanf("%d%d",&a,&b);
grph[a].push_back(b);
invg[b].push_back(a);
}
}
void interpret_data()
{
}
int who[Q];
std::vector<int> go[Q];
bool viz[Q];
int lst[Q];
std::vector<int> mele[Q];
void idfs(int nod,int c)
{
mele[c].push_back(nod);
viz[nod]=0;
who[nod]=c;
for(int i=0; i<invg[nod].size(); i++)
{
if(viz[ invg[nod][i]]==1)
idfs(invg[nod][i],c);
else
go[who[invg[nod][i]]].push_back(c);
}
}
void dfs(int nod)
{
viz[nod]=1;
for(int i=0; i<grph[nod].size(); i++)
{
if(viz[grph[nod][i]]==0)
dfs(grph[nod][i]);
}
lst[++lst[0]]=nod;
}
int cont=0;
void make_tare_conexe()
{
for(int i=1; i<=n; i++)
{
if(viz[i]==0)
{
dfs(i);
}
}
for(int i=n; i>0; i--)
{
if(viz[lst[i]]==1)
{
idfs(lst[i],++cont);
}
}
}
void finisare()
{
printf("%d\n",cont);
for(int j=1; j<=cont; j++)
{
for(int i=0; i<mele[j].size(); i++)
printf("%d ",mele[j][i]);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read_data();
interpret_data();
make_tare_conexe();
finisare();
}