Pagini recente » Cod sursa (job #385924) | Istoria paginii utilizator/ionvladescu | Monitorul de evaluare | Cod sursa (job #1036514) | Cod sursa (job #1016964)
#include <cstdio>
#include <cstring>
#include <vector>
#define N 100005
using namespace std;
struct graf
{
int n;
graf *next;
};
graf *g[N], *gt[N];
int v[N], s[N];
vector <int> sol[N];
int n, k;
void dfs(int x)
{
graf *p;
v[x]=1;
for(p=g[x];p;p=p->next)
{
if(!v[p->n]) dfs(p->n);
}
s[++s[0]]=x;
}
void dfs2(int x)
{
graf *p;
v[x]=1;
sol[k].push_back(x);
for(p=gt[x];p;p=p->next)
{
if(!v[p->n]) dfs2(p->n);
}
}
inline void gadd(graf *g[], int x, int y)
{
graf *p=new graf;
p->n=y;
p->next=g[x];
g[x]=p;
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int i, m, x, y;
vector <int>::iterator it;
scanf("%d%d", &n, &m);
for(i=1;i<=m;i++)
{
scanf("%d%d", &x, &y);
gadd(g, x, y);
gadd(gt, y, x);
}
for(i=1;i<=n;i++)
{
if(!v[i])
{
dfs(i);
}
}
memset(v, 0, sizeof(v));
for(i=n;i;i--)
{
if(!v[s[i]])
{
k++;
dfs2(s[i]);
}
}
printf("%d\n", k);
for(i=1;i<=k;i++)
{
for(it=sol[i].begin();it!=sol[i].end();it++)
{
printf("%d ", *it);
}
printf("\n");
}
}