Pagini recente » Rating Andrei Pop (iRewiewer) | Profil ale_alexia22 | Statistici Beiu Alexandru Dumitru (alexandrel) | Cod sursa (job #1504706) | Cod sursa (job #383840)
Cod sursa(job #383840)
#include<stdio.h>
#include<vector>
#include<algorithm>
#define nmax 100002
using namespace std;
int n,m,nr,st[nmax],viz[nmax];
vector<int> v[nmax];
vector<int> v_t[nmax];
vector<int> sol[nmax];
void dfs(int x)
{
viz[x]=1;
int i,lim=v[x].size();
for(i=0;i<lim;i++)
if(!viz[v[x][i]])
dfs(v[x][i]);
st[++nr]=x;
}
void dfs2(int x)
{
viz[x]=1;
sol[nr].push_back(x);
int i,lim=v_t[x].size();
for(i=0;i<lim;i++)
if(!viz[v_t[x][i]])
dfs2(v_t[x][i]);
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
int i,j,a,b;
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
v_t[b].push_back(a);
}
for(i=1;i<=n;i++)
if(viz[i]==0)
dfs(i);
memset(viz,0,sizeof(viz));
// for(i=1;i<=n;i++)
// fprintf(stderr,"%d ",st[i]);
nr=0;
for(i=n;i>=1;i--)
{
if(!viz[st[i]])
{
++nr;
dfs2(st[i]);
}
}
printf("%d\n",nr);
for(i=1;i<=nr;i++)
{
for(j=0;j<sol[i].size();j++)
printf("%d ",sol[i][j]);
printf("\n");
}
return 0;
}