Pagini recente » Cod sursa (job #2218185) | Cod sursa (job #1540773) | Cod sursa (job #1672907) | Cod sursa (job #2647691) | Cod sursa (job #1647003)
#include <fstream>
#include <cstdio>
#include <vector>
using namespace std;
FILE *fin = fopen ("ctc.in", "r");
ofstream fout ("ctc.out");
vector <int> G[100010], GT[100010], ctc[100010];
int n, m, i, j;
int x, y;
int viz[100010], postordine[100010], unde[100010];
void DFS (int x)
{
int i;
viz[x] = 1;
for (i = 0; i < G[x].size(); i++)
if (viz[G[x][i]] == 0)
DFS (G[x][i]);
postordine[++postordine[0]] = x;
}
void DFST (int x, int nr_ctc)
{
int i;
unde[x] = nr_ctc;
ctc[nr_ctc].push_back (x);
for (i = 0; i < GT[x].size(); i++)
if (unde[GT[x][i]] == 0)
DFST (GT[x][i], nr_ctc);
}
int main()
{
fscanf (fin, "%d %d", &n, &m);
for (i = 1; i <= m; i++)
{
fscanf (fin, "%d %d", &x, &y);
G[x].push_back (y);
GT[y].push_back (x);
}
for (i = 1; i <= n; i++)
if (viz[i] == 0) DFS (i);
int nr_ctc = 0;
for (i = 1; i <= n; i++)
{
if (unde[i] == 0)
{
++nr_ctc;
DFST (i, nr_ctc);
}
}
fout << nr_ctc << '\n';
for (i = 1; i <= nr_ctc; i++)
{
for (j = 0; j < ctc[i].size(); j++) fout << ctc[i][j] << ' ';
fout << '\n';
}
return 0;
}