Pagini recente » Cod sursa (job #478302) | Cod sursa (job #1566962) | Cod sursa (job #2300128) | Cod sursa (job #2273050) | Cod sursa (job #1355573)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <int> g1[100010];
vector <int> g2[100010];
vector <int> postordine;
vector <int> sol[100010];
int m,n,s;
void citire()
{
freopen("ctc.in","r",stdin);
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
g1[a].push_back(b);
g2[b].push_back(a);
}
}
int viz[100010];
int vizctc[100010];
void DFS(int k)
{
for(int i=0;i<g1[k].size();i++)
{
int l=g1[k][i];
g1[k].erase(g1[k].begin()+i,g1[k].begin()+i+1);
i--;
DFS(l);
}
if(!viz[k])
{
postordine.push_back(k);
viz[k]=1;
}
}
void DFSctc(int k)
{
for(int i=0;i<g2[k].size();i++)
{
int l=g2[k][i];
g2[k].erase(g2[k].begin()+i,g2[k].begin()+i+1);
i--;
if(!vizctc[k])
{
sol[s].push_back(k);
vizctc[k]=1;
}
DFSctc(l);
}
}
void ctc()
{
for(int i=1;i<=n;i++)
{
if(g1[i].size())
DFS(i);
}
for(int i=1;i<=n;i++)
if(g2[i].size())
{
s++;
DFSctc(i);
}
}
void afisare()
{
freopen("ctc.out","w",stdout);
printf("%d\n",s);
for(int i=1;i<=s;i++)
{
for(int j=0;j<sol[i].size();j++)
printf("%d ",sol[i][j]);
printf("\n");
}
}
int main()
{
citire();
ctc();
afisare();
return 0;
}