Pagini recente » Cod sursa (job #449713) | Cod sursa (job #1937702) | Cod sursa (job #1329557) | Cod sursa (job #1690134) | Cod sursa (job #1279726)
#include <cstdio>
#include <vector>
#define nmax 100001
#define pb push_back
using namespace std;
vector<int> g[nmax], gt[nmax];
bool viz[nmax];
int n, m, i, k, nr, ordine[nmax], conex[nmax], x, y;
void dfs(int nod)
{
vector <int>::iterator it;
viz[nod]=1;
for(it=g[nod].begin(); it!=g[nod].end(); ++it)
if(!viz[*it]) dfs(*it);
ordine[++k]=nod;
}
void dfst(int nod)
{
conex[nod]=nr;
viz[nod]=0;
vector<int>::iterator it;
for(it=gt[nod].begin(); it!=gt[nod].end(); ++it)
if(viz[*it]) dfst(*it);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d", &n, &m);
for(i=1; i<=m; ++i)
{
scanf("%d%d", &x, &y);
g[x].pb(y);
gt[y].pb(x);
}
for(i=1; i<=n; ++i)
if(!viz[i])
{
dfs(i);
}
for(i=n; i>=1; --i)
if(viz[ordine[i]])
{
++nr;
dfst(ordine[i]);
}
printf("%d\n", nr);
for(i=1; i<=nr; ++i)
{
for(int j=1; j<=n; ++j) if(conex[j]==i) printf("%d ", j);
printf("\n");
}
}