Pagini recente » Cod sursa (job #2512381) | Cod sursa (job #2345635) | Cod sursa (job #4191) | Cod sursa (job #1975643) | Cod sursa (job #2667839)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define in "ctc.in"
#define out "ctc.out"
#define N 100005
vector <bool> d(N+1, 0);
vector <int> LIST[N], LISTT[N], O, C[N];
int n, m, c;
ofstream fout (out);
void DFS (int x)
{
d[x] = 1;
for (unsigned i = 0; i < LIST[x].size(); ++i)
if (!d[LIST[x][i]])
DFS (LIST[x][i]);
O.push_back (x);
}
void DFST (int x)
{
d[x] = 0;
C[c].push_back (x);
for (unsigned i = 0; i < LISTT[x].size(); ++i)
if (d[LISTT[x][i]])
DFST (LISTT[x][i]);
}
int main ()
{
ifstream fin (in);
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
LIST[x].push_back (y);
LISTT[y].push_back (x);
}
fin.close();
for (int i = 1; i <= n; ++i) {
sort (LIST[i].begin(), LIST[i].end());
sort (LISTT[i].begin(), LISTT[i].end());
}
for (int x = 1; x <= n; ++x)
if (!d[x])
DFS (x);
for (int x = n-1; x >= 0; --x)
if (d[O[x]]) {
DFST (O[x]);
c++;
}
ofstream fout (out);
fout << c << "\n";
for (int i = 0; i < c; ++i) {
for (unsigned j = 0; j < C[i].size(); ++j)
fout << C[i][j] << " ";
fout << "\n";
}
return 0;
}