Pagini recente » Cod sursa (job #2882115) | Cod sursa (job #440837) | Cod sursa (job #1587155) | Cod sursa (job #2533825) | Cod sursa (job #2087043)
#include <cstdio>
#include <vector>
using namespace std;
const int NMAX = 100005;
vector <int> G[NMAX];
vector <int> Gt[NMAX], ctc[NMAX];
int nctc, N, M, i, x, y, k, j;
int viz[NMAX], prima[NMAX];
void DFS(int x)
{
viz[x] = 1;
for (int i =0; i < G[x].size(); i++)
if (viz[G[x][i]]==0)
{
DFS(G[x][i]);
}
prima[++k]=x;
}
void DFP(int x)
{
viz[x] = 0;
ctc[nctc].push_back(x);
for (int i =0; i < Gt[x].size(); i++)
if (viz[Gt[x][i]]==1) DFP(Gt[x][i]);
}
int main()
{
freopen("ctc.in", "r", stdin);
freopen("ctc.out", "w", stdout);
scanf("%d%d\n",&N, &M);
for (i=1; i <= M; i++)
{
scanf("%d%d\n", &x, &y);
G[x].push_back(y);
Gt[y].push_back(x);
}
k = 0;
for (i = 1; i <= N; i++)
if (viz[i] == 0) DFS(i);
for (i= N; i >= 1; i-- )
if (viz[prima[i]] == 1)
{
nctc++;
DFP(prima[i]);
}
printf("%d\n", nctc);
for (i = 1; i <= nctc; i++)
{
for (j = 0; j < ctc[i].size(); j++)
printf("%d ",ctc[i][j]);
printf("\n");
}
return 0;
}