Pagini recente » Cod sursa (job #1607915) | Cod sursa (job #1426119) | Cod sursa (job #527783) | Cod sursa (job #1272437) | Cod sursa (job #575352)
Cod sursa(job #575352)
#define LIM 100002
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> Graf[LIM];
vector<int> Trans[LIM];
int PostOrdine[LIM];
bool Vizited[LIM];
int POsize, NrVf;
vector<int> Componente[LIM];
int Csize;
void DFS (int node)
{
Vizited[node] = true;
for (int i=0; i < Graf[node].size(); i++)
if (!Vizited[Graf[node][i]]) DFS(Graf[node][i]);
PostOrdine[++POsize] = node;
}
void DFST (int node)
{
Vizited[node] = false;
Componente[Csize].push_back(node);
for (int i=0; i < Trans[node].size(); i++)
if (Vizited[Trans[node][i]]) DFST(Trans[node][i]);
}
int main()
{
freopen ("ctc.in", "r", stdin);
freopen ("ctc.out", "w", stdout);
int M;
scanf("%d %d\n", &NrVf, &M);
for (int x,y; M > 0; M--)
{
scanf("%d %d\n", &x, &y);
Graf[x].push_back(y);
Trans[y].push_back(x);
}
for (int i=1; i <= NrVf; i++)
if (!Vizited[i]) DFS(i);
for (int i=NrVf; i>0; i--)
if (Vizited[PostOrdine[i]]) {
DFST(PostOrdine[i]);
Csize++;
}
printf("%d\n", Csize);
for (int i=0; i<Csize; i++, printf("\n"))
for (int j=0; j<Componente[i].size(); j++)
printf("%d ", Componente[i][j]);
return 0;
}