Pagini recente » Cod sursa (job #1595667) | Cod sursa (job #321661) | Cod sursa (job #450199) | Cod sursa (job #1520436) | Cod sursa (job #2746268)
#include <fstream>
#include <vector>
int N;
std::vector<int> G[200001];
std::vector<int> GT[200001];
std::vector<int> S;
std::vector<int> C[100001];
int viz[100001];
void dfsG(int k) {
viz[k] = 1;
for (auto& nod : G[k]) {
if (viz[nod] == 0)
dfsG(nod);
}
S.push_back(k);
}
void dfsGT(int k, int nrc) {
viz[k] = 2;
C[nrc].push_back(k);
for (auto& nod : GT[k]) {
if (viz[nod] == 1)
dfsGT(nod, nrc);
}
}
int main() {
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
int M;
fin >> N >> M;
int x, y;
for (int i = 0; i < M; ++i) {
fin >> x >> y;
G[x].push_back(y);
GT[y].push_back(x);
}
fin.close();
for (int i = 1; i <= N; ++i) {
if (viz[i] == 0)
dfsG(i);
}
int nrc = 0;
for (auto&& it = S.rbegin(); it != S.rend(); ++it) {
if (viz[*it] == 1) {
++nrc;
dfsGT(*it, nrc);
}
}
fout << nrc << '\n';
for (int i = 1; i <= nrc; ++i) {
for (auto& nod : C[i])
fout << nod << ' ';
fout << '\n';
}
fout.close();
return 0;
}