Pagini recente » Cod sursa (job #2090769) | Cod sursa (job #728851) | Cod sursa (job #2421186) | Cod sursa (job #1397686) | Cod sursa (job #2097173)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
int n, m;
vector<vector<int> > gr(100100);
vector<vector<int> > inv(100100);
vector<bool> used(100100);
vector<vector<int> > ans;
vector<int> verif;
vector<int> comp;
void dfs(int root) {
used[root] = true;
for (auto &x : gr[root]) {
if (!used[x]) {
dfs(x);
}
}
verif.push_back(root);
}
void DFS(int root) {
used[root] = true;
comp.push_back(root);
for (auto &x : inv[root]) {
if (!used[x]) {
DFS(x);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
gr[a].push_back(b);
inv[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (used[i]) {
continue;
}
dfs(i);
}
for (int i = 1; i <= n; i++) {
used[i] = false;
}
reverse (verif.begin() , verif.end());
for (auto &x : verif){
if (!used[x]){
comp.clear();
DFS(x);
ans.push_back(comp);
}
}
cout << ans.size() << '\n';
for (auto &x : ans) {
for (auto &y : x) {
cout << y << " ";
}
cout << '\n';
}
return 0;
}