Pagini recente » Cod sursa (job #3148847) | Cod sursa (job #2966014) | Cod sursa (job #3245134) | Cod sursa (job #3254248) | Cod sursa (job #389574)
Cod sursa(job #389574)
#include <cstdio>
#include <vector>
using namespace std;
#define file_in "ctc.in"
#define file_out "ctc.out"
#define Nmax 101010
int n,m,ord[Nmax],sol,nr,viz[Nmax];
vector<int> G1[Nmax],G2[Nmax],v[Nmax];
void dfs(int nod)
{
if (viz[nod]==1)
return ;
viz[nod]=1;
for (int i=0;i<G1[nod].size();++i)
if (!viz[G1[nod][i]])
dfs(G1[nod][i]);
ord[++nr]=nod;
}
void dfs2(int nod)
{
if (viz[nod]==1)
return ;
v[sol].push_back(nod);
viz[nod]=1;
for (int i=0;i<G2[nod].size();++i)
if (!viz[G2[nod][i]])
dfs2(G2[nod][i]);
}
int main()
{
int i,a,b,j;
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d", &n, &m);
for (i=1;i<=m;++i)
{
scanf("%d %d", &a, &b);
G1[a].push_back(b);
G2[b].push_back(a);
}
memset(viz,0,sizeof(viz));
nr=0;
for (i=1;i<=n;++i)
if (!viz[i])
dfs(i);
memset(viz,0,sizeof(viz));
sol=0;
for (i=n;i>=1;--i)
if (!viz[ord[i]])
{
sol++;
dfs2(ord[i]);
}
printf("%d\n", sol);
for (i=1;i<=nr;++i)
{
for (j=0;j<v[i].size();++j)
printf("%d ", v[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}