Pagini recente » Cod sursa (job #3219915) | Cod sursa (job #1545417) | Cod sursa (job #1047123) | Cod sursa (job #2384833) | Cod sursa (job #3212058)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int nmax = 1e5;
vector<vector<int>> ctc;
vector<int> edge[nmax + 1], egde[nmax + 1];
vector<bool> viz(nmax + 1, 0);
vector<int> topo(1, 0);
int n, m, x, y;
void read() {
fin >> n >> m;
for(int i = 1; i <= m; i++) {
fin >> x >> y;
edge[x].pb(y);
egde[y].pb(x);
}
}
void dfs(int nod) {
viz[nod] = 1;
for(int fiul : edge[nod]) {
if(viz[fiul] == 0)
dfs(fiul);
}
topo.pb(nod);
}
void sfd(int nod) {
viz[nod] = 1;
ctc.back().pb(nod);
for(int fiul : egde[nod]) {
if(viz[fiul] == 0)
sfd(fiul);
}
}
void print() {
fout << ctc.size() << "\n";
for(int cur = 0; cur < ctc.size(); cur++) {
for(auto val : ctc[cur])
fout << val << " ";
fout << "\n";
}
}
void comp_ctc() {
for(int i = 1; i <= n; i++) {
if(viz[i] == 0)
dfs(i);
}
viz = vector<bool>(nmax + 1, 0);
for(int i = n; i >= 1; i--) {
int cur = topo[i];
if(viz[cur] == 0) {
ctc.pb(vector<int>());
sfd(cur);
}
}
}
int main() {
read();
comp_ctc();
print();
return 0;
}