Pagini recente » Cod sursa (job #3222005) | Cod sursa (job #3259784) | Cod sursa (job #618421) | Cod sursa (job #3233350) | Cod sursa (job #245419)
Cod sursa(job #245419)
#include <stdio.h>
#include <assert.h>
#include <vector>
using namespace std;
#define maxn 100010
int N, M, L, NR;
vector <int> A[maxn], T[maxn];
int G[maxn], GT[maxn], S[maxn];
char u[maxn];
vector <int> CMP[maxn];
inline void DFS(int nod)
{
int i;
u[nod] = 1;
for (i=0; i<G[nod]; i++)
if (!u[A[nod][i]]) DFS(A[nod][i]);
S[++L] = nod;
}
inline void DFS2(int nod)
{
int i;
u[nod] = 2;
CMP[NR].push_back(nod);
for (i=0; i<GT[nod]; i++)
if (u[T[nod][i]] != 2) DFS2(T[nod][i]);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
int i, j, x, y;
scanf("%d %d ", &N, &M);
// assert(1<=N && N<=100000);
// assert(1<=M && M<=200000);
for (i=1; i<=M; i++)
{
scanf("%d %d ", &x, &y);
// assert(1<=x && x<=N);
// assert(1<=y && y<=N);
A[x].push_back(y);
T[y].push_back(x);
}
for (i=1; i<=N; i++)
{
G[i] = A[i].size();
GT[i] = T[i].size();
}
for (i=1; i<=N; i++)
if (!u[i]) DFS(i);
for (i=N; i>0; i--)
if (u[S[i]] != 2)
{
NR++;
DFS2(S[i]);
}
printf("%d\n", NR);
for (i=1; i<=NR; i++)
{
L = CMP[i].size();
for (j=0; j<L; j++) printf("%d ", CMP[i][j]);
printf("\n");
}
return 0;
}