Pagini recente » Cod sursa (job #17834) | Cod sursa (job #481137) | Cod sursa (job #1214558) | Cod sursa (job #2777603) | Cod sursa (job #2489269)
#include<cstdio>
#include<vector>
using namespace std;
const int NMAX = 100000;
vector<int>v[NMAX + 1];
vector<int>pred[NMAX + 1];
vector<int>v2;
vector<int>mat[NMAX + 1];
bool viz[NMAX + 1];
void dfs(int nod)
{
viz[nod] = 1;
for(int i = 0 ; i < v[nod].size() ; i ++)
{
if(viz[v[nod][i]] == 0)
dfs(v[nod][i]);
}
v2.push_back(nod);
}
void dfs2(int nod ,int lin)
{
viz[nod] = 1;
for(int i = 0 ; i < pred[nod].size() ; i ++)
{
if(viz[pred[nod][i]] == 0)
dfs2(pred[nod][i] , lin);
}
mat[lin].push_back(nod);
}
int main()
{
int n , m , x , y;
freopen("ctc.in" , "r" , stdin);
freopen("ctc.out" , "w" , stdout);
scanf("%d%d" , &n , &m);
for(int i = 1; i <= m ; i ++)
{
scanf("%d%d" , &x, &y);
v[x].push_back(y);
pred[y].push_back(x);
}
for(int i = 1; i <= n ; i ++)
if(viz[i] == 0)
dfs(i);
for(int i = 0; i <= n ; i ++)
viz[i] = 0;
int k = 0;
for(int i = n - 1; i >= 0 ; i --)
{
if(viz[v2[i]] == 0)
dfs2(v2[i] , ++k);
}
printf("%d\n" , k);
for(int i = 1; i <= k ; i ++){
for(int j = 0 ; j < mat[i].size() ; j ++)
printf("%d " , mat[i][j]);
printf("\n");
}
return 0;
}