Pagini recente » Cod sursa (job #665061) | Cod sursa (job #1993857) | Cod sursa (job #1260261) | Cod sursa (job #70540) | Cod sursa (job #422239)
Cod sursa(job #422239)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define pb push_back
using namespace std;
struct triplet
{
int ti,to,nod;
};
vector <int> pred[100100],succ[100100],ct[100100];
triplet t[100100];
int n,m,timp,cnt;
bool v[100100];
bool comp(const triplet &a,const triplet &b)
{
return a.to>b.to;
}
void dfsinv(int nod)
{
v[nod]=true;
ct[cnt].pb(nod);
for (int i=0;i!=pred[nod].size();++i)
if (!v[pred[nod][i]])
dfsinv(pred[nod][i]);
}
void dfs(int nod)
{
t[nod].nod=nod;
t[nod].ti=++timp;
v[nod]=true;
for (int i=0;i!=succ[nod].size();++i)
if (!v[succ[nod][i]])
dfs(succ[nod][i]);
t[nod].to=++timp;
}
void citire()
{
scanf("%d%d",&n,&m);
int x,y;
for (int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
pred[y].pb(x);
succ[x].pb(y);
}
}
void scrie()
{
printf("%d\n",cnt);
for (int i=1;ct[i].size();++i)
{
for (int j=0;j!=ct[i].size();++j)
printf("%d ",ct[i][j]);
printf("\n");
}
}
int main()
{
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
citire();
for (int i=1;i<=n;++i)
if (!v[i])
dfs(i);
sort(t+1,t+n+1,comp);
memset(v,0,sizeof(v));
for (int i=1;i<=n;++i)
if (!v[t[i].nod])
{
++cnt;
dfsinv(t[i].nod);
}
scrie();
return 0;
}