Pagini recente » Cod sursa (job #427910) | Cod sursa (job #2549478) | Cod sursa (job #1182422) | Cod sursa (job #2141686) | Cod sursa (job #757452)
Cod sursa(job #757452)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define MAXN 100100
vector<int> Gi[MAXN], Go[MAXN], stiva, rez[MAXN];
int n, m, used[MAXN], comp[MAXN];
void DF1(int nod) {
used[nod] = 1;
for (int i = 0; i < Gi[nod].size(); ++i) {
if (!used[Gi[nod][i]])
DF1(Gi[nod][i]);
}
stiva.push_back(nod);
}
void DF2(int nod, int v) {
comp[nod] = v;
for (int i = 0; i < Go[nod].size(); ++i) {
if (comp[Go[nod][i]] == 0)
DF2(Go[nod][i], v);
}
}
int main() {
int i, cnt = 0, j, x, y;
fin >> n >> m;
for (i = 1; i <= m; ++i) {
fin >> x >> y;
Gi[x].push_back(y);
Go[y].push_back(x);
}
for (i = 1; i <= n; ++i)
if (!used[i])
DF1(i);
for (; stiva.size(); stiva.pop_back())
if (comp[stiva.back()] == 0)
DF2(stiva.back(), ++cnt);
for (i = 1; i <= n; ++i)
rez[comp[i]].push_back(i);
fout << cnt << "\n";
for (i = 1; i <= cnt; ++i) {
for (j = 0; j < rez[i].size(); ++j)
fout << rez[i][j] << " ";
fout << "\n";
}
return 0;
}