Pagini recente » Cod sursa (job #182372) | Cod sursa (job #3203390) | Cod sursa (job #2310914) | Cod sursa (job #181251) | Cod sursa (job #1913897)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
const int NMAX = 100010;
const int MMAX = 200010;
int N, M;
vector<int> G[NMAX];
vector<int> T[NMAX];
vector<int> ord;
vector<int> ctc[NMAX];
int viz1[NMAX];
void DFS1 (int nod) {
viz1[nod] = 1;
ord.push_back(nod);
for (auto &it : G[nod]) {
if ( !viz1[it]) {
DFS1(it);
}
}
}
int viz2[NMAX];
void DFS2 (int nod, int indCtc) {
viz2[nod] = 1;
ctc[indCtc].push_back (nod);
for (auto &it : T[nod]) {
if ( !viz2[it]) {
DFS2(it, indCtc);
}
}
}
int main () {
fin >> N >> M;
for (int i = 1; i <= M; i++) {
int x, y;
fin >> x >> y;
G[x].push_back (y);
T[y].push_back (x);
}
for (int i = 1; i <= N; i++) {
if ( !viz1[i]) {
DFS1 (i);
}
}
int nrCtc = 0;
for (auto &it : ord) {
if ( !viz2[it]) {
nrCtc ++;
DFS2 (it, nrCtc);
}
}
fout << nrCtc << '\n';
for (int i = 1; i <= nrCtc; i++) {
for (auto &it : ctc[i]) {
fout << it << " ";
}
fout << '\n';
}
return 0;
}