Pagini recente » Cod sursa (job #1997412) | Cod sursa (job #3292728) | Cod sursa (job #2524098) | Cod sursa (job #1453950) | Cod sursa (job #1650457)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100009;
int marked[nmax] , st[nmax];
vector < int > g[nmax] , t[nmax] , ctc[nmax];
int top , S , i , n , m , a , b , j;
void dfG(int x)
{
marked[x] = true;
for (int i = 0 ; i < g[x].size() ; ++i)
{
int y = g[x][i];
if (marked[y]) continue;
dfG(y);
}
st[++top] = x;
}
void dfT(int x)
{
ctc[S].push_back(x);
marked[x] = false;
for (int i = 0 ; i < t[x].size() ; ++i)
{
int y = t[x][i];
if (!marked[y]) continue;
dfT(y);
}
}
int main()
{
freopen("ctc.in" , "r" , stdin);
freopen("ctc.out" , "w" , stdout);
scanf("%d" , &n);
scanf("%d" , &m);
for (i = 1 ; i <= m ; ++i)
{
scanf("%d" , &a);
scanf("%d" , &b);
g[a].push_back(b);
t[b].push_back(a);
}
for (i = 1 ; i <= n ; ++i)
if (!marked[i]) dfG(i);
while (top)
{
if (marked[st[top]])
{
++S;
dfT(st[top]);
}
top--;
}
printf("%d\n" , S);
for (i = 1 ; i <= S ; ++i)
{
for (j = 0 ; j < ctc[i].size() ; ++j)
printf("%d " , ctc[i][j]);
printf("\n");
}
return 0;
}